A recent blog post by Erwin Kalvelagen discusses a very straightforward integer programming problem. You have a rectangular grid of boolean variables, where a variables neighbors are the variable immediately above, below, to the left or to the right of it. The sole constraint is that, for any cell, at least one of that cell's variable or its neighbor variables must be true. The objective is to minimize the number of true cells in the grid. Erwin coded the model in GAMS and ran it for a 32x32 grid. He reported that he got an incumbent value of 227 in about 65 seconds but had trouble getting to optimality. (This might be a good time to point out that Erwin's computer is probably better than mine, since he is a consultant.)
I was curious whether a couple of redundant constraints would help. The problem suffers (if that is the correct term) from symmetry. Draw a grid and color in the cells of an optimal solution. Now flip the grid, switching either top with bottom, left with right, or both. The colored cells still form an optimal solution. What is the harm of symmetry? Think about the branch-and-bound (or, if you prefer, branch-and-cut) algorithm and specifically how it prunes nodes based on bound. When you find a new incumbent solution, you prune any node whose bound is no better than that solution. Typically the node bound will be at least slightly loose (meaning, in a minimization problem, that the bound will be strictly less than the objective value of the best feasible solution lurking in that node). In the context of the current problem, when a feasible solution is found, there will be at least three other feasible solutions with the same objective value, obtained by reversing the indexing of rows, columns or both. Each of them will likely be in a node of the search tree with an objective value at least slightly better than their true value, meaning that none of those nodes can be pruned right away, even if they do not contain an even better solution.
So symmetry can slow pruning and also slow improvement of the best bound. There has been research on how to exploit symmetry in IP models, but as far as I know that work has to be baked into a solver to be used. At least some solvers have some built-in capability to recognize and deal with symmetry, but I'm not sure how well that works. I usually keep an eye out for symmetry and, if I think it might be slowing improvement of the bound, see if I can constrain away some of it.
In this case, the symmetry I identified can be removed by adding just two constraints. One is that the number of true cells in the top row should not exceed the number in the bottom row (so that the vertical flip is ruled out unless the top and bottom rows are tied). Similarly, the other is that the number of true cells in the left column should not exceed the number in the right column (ruling out the horizontal flip). Since these constraints shrink the feasible region, it would not be surprising if they slow down identification of improved incumbents. By enlarging the model, they also slow down (very slightly?) the rate at which nodes are solved. The hope is that faster bound improvements compensate for that.
I ran the 32x32 case (coded in Java) using two solvers, FICO Xpress MP (version 44.01.01) and IBM CPLEX (version 22.1.2), both with and without the antisymmetry constraints. Each run was limited to 15 minutes (wall clock time) and used default settings for all parameters. Here are the results, in the format "best solution/best bound".
| Xpress MP | CPLEX | |
|---|---|---|
| With antisymmetry | 231 / 215.73 | 227 / 214.40 |
| Without antisymmetry | 228 / 215.95 | 229 / 214.38 |
There is enough randomness in IP solvers that I would not read much into a single iteration of each model. CPLEX actually did a bit better on the incumbent with the antisymmetry constraints included, which surprises me. Xpress had a very slightly worse bound with them included, which also surprises me. The bottom line seems to be that the antisymmetry constraints do not help much (which I find disappointing) and that, as Erwin noted, the problem is a bit stubborn.
As always, my code is available for download.
Might be worth imposing a third symmetry-breaking constraint for the colored cells above versus below the main diagonal.
ReplyDeleteMight be worth a try, although I would think the combination of the first two symmetries would encompass the third one. Also, the added constraint would be pretty dense. I'll give it a try.
DeleteOh, I had misread as top half versus bottom half, rather than top row versus bottom row. To impose a sparse third constraint (which should be independent of the other two), you could break symmetry via superdiagonal versus subdiagonal.
ReplyDeleteWorth a try, with one caveat. Mirroring the grid around its horizontal respectively vertical axis does not change which cells are in the top and bottom respectively left and right edges. Mirroring around the diagonal, however, does: the top left cell stays top left but the bottom left cell becomes top right. So I don't think mirroring around the diagonal can be combined with the other two antisymmetry constraints (which are safe to combine with each other). I'll try diagonal mirroring and see if it helps.
DeleteXpress would detect this kind of symmetry, since it is only about swapping certain variables with each other. This explains why the solution times don't really improve for either solver.
ReplyDeleteAs to the diagonal third constraint: it is valid to add a constraint that says that the top row has at least as many true cells as the left column.
If top row has fewer than bottom row, flip along the horizontal axis.
If the left column has fewer than the right column, flip along the vertical axis. This leaves the top/bottom relation unchanged.
If the top row has fewer than the left column, flip along the main diagonal. This leaves both of the previous relations unchanged. The top will still have at least as many as the bottom, and the left will have at least as many as the right.
So if we have a feasible solution, we can always get another one where the top row has the most true cells of all the border rows/columns, and the left column has more than the right column.
Thanks. I'm going to test adding your third constraint to my original two. I suspect, though, that eliminating symmetry will turn out to be counterproductive (unlike in my misspent youth when it was critical). I noticed that Xpress puts orbit counts in the output, which I suspect means it has orbital branching baked in (and actually possibly benefits from the symmetry?).
Delete