As the title implies, this is a sequel to my previous post, to deal with a variety of odds and ends.
There's a saying that you cannot teach an old dog new tricks. That's untrue; it's just that dogs as old as I am are slow learners. When I first started tangling with integer programs, there was a rule that you never made the model dimensions (number of rows or columns) any larger than you absolutely had to, partly to conserve memory and partly so as not to slow down pivoting. Once solvers switched from Gaussian pivoting (the way I learned to do it by hand) to matrix factoring, keeping dimensions down took a back seat to reducing matrix density.
Similarly, once upon a time I learned (the hard way) that symmetry in my model would slow down pruning of the search tree. In the previous post, I alluded to research on exploiting symmetry and said something about solvers having symmetry detection. Imre Polik mentioned in a comment that Xpress already detects the symmetry by default. CPLEX might need some encouragement to do so. Near the start of the Xpress output, it describes the model as symmetric and lists statistics on "orbits" (groups of variables whose values can be permuted). It is unclear to me whether Xpress exploits that information by using "orbital branching" (a relatively recent development) or in some other way. Early in the CPLEX output I see a message that it is "detecting symmetries", but the model dimensions do not change and there are no further mentions of symmetry.
Moving on, Imre suggested in his comment to the previous post that another possible antisymmetry constraint is to assert a dominance inequality between the number of true values in the top row and the number in the left column. This is compatible with my original two constraints, and so I added a version of it (combining Imre's constraint with mine) to my code. Rob Pratt suggested yet another possibility, an inequality between the subdiagonal and superdiagonal. I'm not convinced that one plays nice with my original constraints, meaning that if you added Rob's constraint to my original two you might legislate the optimal solution out of existence, so I added it to my code by itself. Also, it only works when the grid is square. Finally, since both solvers have parameters to control how hard they work to detect symmetry, I added an option to my code to skip adding any constraints and just crank up the solver's response.
The results are summarized in the following graph, which shows the optimality gap (best bound at the left end, best incumbent at the right end) for each solver and modeling option. The dashed vertical line is the optimal solution (from Erwin's post).
The "Bilateral" and "Trilateral" models are my original two constraints and my two constraints plus Imre's, respectively. The "Diagonal" model uses Rob's constraint. "None" is just the model by itself and "Solver" is the unmodified model plus a solver parameter setting to get it to work harder detecting symmetries. Note that the results for Xpress with "None" and Xpress with "Solver" are pretty much identical, confirming Imre's assertion that Xpress would detect the symmetry on its own. CPLEX saw a bit of improvement in both incumbent and bound going from "None" to "Solver", so apparently the nudge helped there. Only two runs found the optimal solution, both times CPLEX with some help from antisymmetry constraints. None of the runs got the best bound anywhere near tight.
Returning to my "old dog, new tricks" theme, the takeaway for me is that before I go nuts try to constrain away symmetry in a model, I need to investigate whether the solver can recognize it and, if so, whether it can eliminate or even exploit the symmetry.
Lastly, I belatedly realized that Erwin got his proven optimum quickly because the modified the model to use equality constraints in the interior of the grid and inequalities only in the two outermost rows/columns on each edge. I added that to my code as well, and yes, it gets a proven optimum incredibly fast. I was a bit leery about assuming that redundant coverage would only be required near the boundary, but per some comments by Rob on Erwin's post, 227 is indeed the (known) optimal value for a 32x32 grid.
The problem with these symmetry breaking constraints is that they cannot deal with the equality case, unless you can argue that by parity or something an equality cannot happen.
ReplyDeleteFor instance, adding the constraint that the top row has at least as many ones as the bottom row is quite useless for all the cases that the two rows have the same number of nonzeros.
With orbital branching (and probing, and other symmetry based reduction techniques) one we have checked that the top row with k nonzeros has a certain objective, we can rule out any solution where any border row/column has k nonzeros, because they cannot yield a better objective. The symmetry breaking constraints don't get this, but they disable the built-in symmetry handling, so they may hurt more than they help.
Thanks, that makes a lot of sense. I've always known that the added constraints don't break ties, but figured that "half a loaf is better than none" (meaning that if they eliminated equivalent solutions where there weren't ties it would help). The constraints interfering with orbital branching etc. raises a question. Suppose that symmetric solutions do not involve ties (such as same count in top and bottom rows). In that case, does orbital branching etc. still work better than the symmetry breaking constraints, or are the constraints more effective? If the constraints are less effective even without ties, it's a clear choice: omit them. If they do better without ties (but worse with ties) then either choice seems to be a bit of a gamble.
DeleteIf the symmetry is between binary variables, and it consists only of swapping them, then it doesn't make sense to add symmetry breaking constraints, because the solvers will detect and handle it. If the symmetry involves taking the complement of some binaries, then it is better to break that in the model.
DeleteA similar case I had was when trying to place points in the unit square and optimizing some geometric objective. We can always assume that there will be at least one point in the lower left quadrant of the square, so we can tighten the bounds on one variable to [0, 1/2], but this wouldn't be found by symmetry detection in any solver I know.