I have grid of dimensions H and W of boolean variables. The only constraint is that if a variable is false then at least one of the adjacent variables (top, right, left, bottom, diagonals don't count) must be true. The goal is to minimize the number of true values in the grid.
High-level model |
---|
\[\begin{align}\min&\sum_{i,j}\color{darkred}x_{i,j}\\ & \color{darkred}x_{i,j}=0 \implies \color{darkred}x_{i-1,j} + \color{darkred}x_{i+1,j} + \color{darkred}x_{i,j-1} + \color{darkred}x_{i,j+1} \ge 1 \\ & \color{darkred}x_{i,j}\in \{0,1\} \end{align}\] |
The implication can be written as a simple linear constraint: \[ \color{darkred}x_{i-1,j} + \color{darkred}x_{i+1,j} + \color{darkred}x_{i,j-1} + \color{darkred}x_{i,j+1} \ge 1 - \color{darkred}x_{i,j}\] or \[ \color{darkred}x_{i,j} + \color{darkred}x_{i-1,j} + \color{darkred}x_{i+1,j} + \color{darkred}x_{i,j-1} + \color{darkred}x_{i,j+1} \ge 1 \] We can also find the last constraint directly from the description. Just a different way of looking at the problem statement: at least one from \(\color{darkred}x_{i,j}\) and its direct neighbors should be 1.
seti 'rows' /row1*row32/j 'columns' /col1*col32/;variable z 'objective';binary variable x(i,j) 'cells';equationsobj 'objective'eq(i,j) 'implication';obj.. z =e= sum((i,j),x(i,j));eq(i,j).. x(i,j) + x(i-1,j) + x(i+1,j) + x(i,j-1) + x(i,j+1) =g= 1;model m /all/;solve m minimizing z using mip;option x:0:1:1;display x.l;
A model with just 1024 binary variables can be difficult even for high-end solvers. Of course \(2^{1024}\) is not that small:
Improvement
One way to improve on the performance is to notice that the interior is rather regular and that the behavior near the border is more unpredictable. That makes sense as we assume all values outside the board are zero. That makes the constraint more difficult to obey on or near the border. My idea is to write the equations as:
\[\begin{align} & \color{darkred}x_{i,j} + \color{darkred}x_{i-1,j} + \color{darkred}x_{i+1,j} + \color{darkred}x_{i,j-1} + \color{darkred}x_{i,j+1} = 1 && \text{for $(i,j)$ in the interior part} \\ & \color{darkred}x_{i,j} + \color{darkred}x_{i-1,j} + \color{darkred}x_{i+1,j} + \color{darkred}x_{i,j-1} + \color{darkred}x_{i,j+1} \ge 1 && \text{for $(i,j)$ near the border}\end{align}\]
I define here the border region as the first and last two rows and columns. The depth of the border region needed to be two levels. When using a skinny border of just one cell, the model was infeasible. This version of the model is solved very fast (0.6 seconds; zero nodes were needed and only 141 simplex iterations, with proven optimality). It is quite remarkable how much impact this new formulation has on the performance. We are talking about a > 6000x performance increase. The picture becomes:
Complete GAMS Model
Known solutions
References
- Suggestion on which constraint to adds to optimize Minizinc's model, https://stackoverflow.com/questions/78987960/suggestion-on-which-constraint-to-adds-to-optimize-minizincs-model
This is the domination number of an n by n grid graph, and the values are known for all n: https://oeis.org/A104519
ReplyDeleteThanks. Not 100% the same as my model, but very close.
DeleteHmm, I don't see any difference. For domination number, the problem is to minimize the number of selected nodes subject to a constraint for each node that either the node or at least one of its neighbors is selected. That yields the same formulation as your problem.
DeleteFor a 3x3 grid I need 3 ones.
DeleteYes, 3x3 corresponds to a(3+2) = a(5) = 3 in OEIS: "COMMENTS a(n+2) is also the domination number (size of minimum dominating set) in an n X n grid graph (Alanko et al.)."
DeleteAh, I missed "a(n+2) is also the domination number".
Delete