Orthogonally neigboring cells differ in value by at most 5
This max 5 difference is a convex constraint, so it can be expressed quite easily: \[-5 \le v_{i,j} - v_{i',j'} \le 5\] for neighboring cells \((i,j)\) and \((i',j')\).
A more difficult restriction is: neighboring cells must differ by at least 2. Here is such a problem, again designed by Aad van de Wetering:
 |
| Problem data |
The rules are:
- Standard Sudoku-rules apply. cells in each row, column and sub-block have unique values from 1 through 9.
- In addition, neighboring (horizontal and vertical) cells have values that differ by 2 or more.
- Also, values 1 and 9 are considered to have a difference of 1. So neighboring cells, cannot have values 1 and 9.
I will try to solve this problem in two different ways. The first is an extension of what we did in [1]. The second one is a bit different.
Approach I
The constraint: neighbors must be different by at least two, can be formalized as \[\left| v_{i,j} - v_{i',j'} \right| \ge 2\] for neighboring cells \((i,j)\) and \((i',j')\). The non-convexity of this constraint \[\begin{align} & v_{i,j} - v_{i',j'} \ge 2 \\ & \mathbf{or} \\&v_{i,'j'} - v_{i,j} \ge 2 \end{align} \] requires extra binary variables and big-M constraints: \[\begin{align} & v_{i,j} - v_{i',j'} \ge 2 - M\cdot \delta_{i,j,i',j'} \\ & v_{i,'j'} - v_{i,j} \ge 2 - M\cdot (1-\delta_{i,j,i',j'})\\ & \delta_{i,j,i',j'} \in \{0,1\}\end{align}\] So, how large should \(M\) be? The maximum difference between two different values is 8. So we need \(2-M\le -8\) or \(M=10\).
We ignored that values 1 and 9 also have a difference of 1. As all other combinations are allowed, we can handle this by \[\left|v_{i,j}-v_{i',j'}\right| \le 7\] This is a constraint we already know how to handle: \[-7 \le v_{i,j}-v_{i',j'} \le 7\] Interestingly, this addition restriction also can help us in tightening our big-M value. We can now use \(M = 9\). Note that with this smaller big-M we still need this constraint: the big-M constraint only covers one of the needed two sides of this constraint.
The complete model can look like:
We ignored that values 1 and 9 also have a difference of 1. As all other combinations are allowed, we can handle this by \[\left|v_{i,j}-v_{i',j'}\right| \le 7\] This is a constraint we already know how to handle: \[-7 \le v_{i,j}-v_{i',j'} \le 7\] Interestingly, this addition restriction also can help us in tightening our big-M value. We can now use \(M = 9\). Note that with this smaller big-M we still need this constraint: the big-M constraint only covers one of the needed two sides of this constraint.
The complete model can look like:
| Mixed-Integer Programming Model I |
|---|
| \[\begin{align}\min\>& 0 && && \text{Dummy objective}\\ & \sum_k \color{darkred}x_{i,j,k} = 1 &&\forall i,j && \text{One $k$ in each cell}\\ & \sum_{i,j|\color{darkblue}u_{a,i,j}} \color{darkred}x_{i,j,k} = 1 && \forall a,k && \text{Unique values in each area}\\ &\color{darkred}v_{i,j} =\sum_k \color{darkblue}k\cdot\color{darkred}x_{i,j,k} && \forall i,j &&\text{Value of cell}\\ & \color{darkred}v_{i,j} - \color{darkred}v_{i',j'} \ge 2 - \color{darkblue}M\cdot \color{darkred}\delta_{i,j,i',j'}&&\forall i,j,i',j'|\color{darkblue}{nb}_{i,j,i',j'} &&\text{Min difference of 2} \\ & \color{darkred}v_{i,'j'} - \color{darkred}v_{i,j} \ge 2 - \color{darkblue}M\cdot (1-\color{darkred}\delta_{i,j,i',j'}) &&\forall i,j,i',j'|\color{darkblue}{nb}_{i,j,i',j'}\\ & -7 \le \color{darkred}v_{i,j} - \color{darkred}v_{i',j'} \le 7 &&\forall i,j,i',j'|\color{darkblue}{nb}_{i,j,i',j'} && \text{Neighbors differ by max 7} \\ & \color{darkred}x_{i,j,k} = 1 && \text{where } k=\color{darkblue}{\mathit{Given}}_{i,j} &&\text{Fix given values}\\&\color{darkred}x_{i,j,k} \in \{0,1\} \\ &\color{darkred}v_{i,j} \in \{1,\dots,9\} \\ & \color{darkred}\delta_{i,j,i',j'} \in \{0,1\} \\ & \color{darkblue}M = 9\end{align}\] |
Notes:
- This model solves quickly: the presolve can remove all rows and columns.
- The solution is unique (see [1]).
- Using the above data set we actually can drop the "max 7" constraint. I think that is just a property of this data set. In general, we should include this constraint.
Approach II
A simpler approach is to consider the pairs of values that cannot be neighbors: \[(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,1)\] We also need to add their symmetrical counterparts \[(2,1),(3,2),\dots\] Detail: this is due to the way we organized the neighbors. The neighbor set did not have both: i.e. cells \(\text{$(1,2)$-$(1,3)$}\) are neighbors, so this is stored. But, I did not also store the combination \(\text{$(1,3)$-$(1,2)$}\).
After automatically generating the combinations \((k,k')\) that we need to prevent, the forbid data can look like:
---- 55 SET forbid combinations of values we want to exclude
v1 v2 v3 v4 v5 v6 v7 v8 v9
v1 YES YES
v2 YES YES
v3 YES YES
v4 YES YES
v5 YES YES
v6 YES YES
v7 YES YES
v8 YES YES
v9 YES YES
This table contains elements \(\mathit{forbid}_{k,k'}\) we want to forbid. Note that we can exclude the diagonal from this: neighboring cells already cannot have the same value. For this set of value-pairs, we want to add the constraint:\[x_{i,j,k} + x_{i',j',k'} \le 1 \] for all neighboring cells \((i,j)\) and \((i',j')\) and for all forbidden value combinations \((k,k')\). We have 18 of these combinations and 144 neighbors to check, yielding 2592 of these constraints.
The full model can look like:
| Mixed-Integer Programming Model II |
|---|
| \[\begin{align}\min\>& 0 && && \text{Dummy objective}\\ & \sum_k \color{darkred}x_{i,j,k} = 1 &&\forall i,j && \text{One $k$ in each cell}\\ & \sum_{i,j|\color{darkblue}u_{a,i,j}} \color{darkred}x_{i,j,k} = 1 && \forall a,k && \text{Unique values in each area}\\ & \color{darkred}x_{i,j,k} + \color{darkred}x_{i',j',k'} \le 1 && \begin{aligned}& \forall i,j,i',j'|\color{darkblue}{nb}_{i,j,i',j'} \\ & \forall k,k'|\color{darkblue}{\mathit{forbid}}_{k,k'} \end{aligned}&&\text{Forbid combinations} \\ & \color{darkred}x_{i,j,k} = 1 && \text{where } k=\color{darkblue}{\mathit{Given}}_{i,j} &&\text{Fix given values}\\&\color{darkred}x_{i,j,k} \in \{0,1\} \end{align}\] |
When we run this model, we will see the solution:
---- 84 PARAMETER v values (postprocessing) c1 c2 c3 c4 c5 c6 c7 c8 c9 r1 9 2 6 4 1 7 3 5 8 r2 3 5 8 2 6 9 7 1 4 r3 1 7 4 8 3 5 2 6 9 r4 7 4 1 6 9 2 5 8 3 r5 5 8 3 1 7 4 9 2 6 r6 2 6 9 3 5 8 4 7 1 r7 6 9 2 5 8 3 1 4 7 r8 8 3 5 7 4 1 6 9 2 r9 4 1 7 9 2 6 8 3 5
This solution is unique. The presolver completely solves the model, so no actual iterations are performed.
No comments:
Post a Comment