Saturday, December 8, 2018

More queens problems

In [1] the famous \(n\)-queens problem was discussed: how many queens can we place on a chess-board such that non of them are attacked by others. Interestingly, we had some non-obvious problem with Cplex enumerating the different configurations (due to tolerance issues).

A different problem is the Minimum Dominating Set of Queens Problem:
Find the minimum number of queens needed such that they dominate each square.
Here dominate means: either a square is under attack by at least one queen, or it is occupied by a queen.

To develop a Mixed Integer Programming model, we introduce the familiar binary variables:

\[x_{i,j} = \begin{cases} 1 & \text{if square \((i,j)\) is occupied by a queen}\\ 0 & \text{otherwise}\end{cases}\]

A square \((i,j)\) is dominated if:

  1. \(x_{i,j}=1\): a queen is located here. This case will be covered by the following other cases, so we don't have to worry about this.
  2. There is a queen in row \(i\): \[\sum_{j'} x_{i,j'} \ge 1\]
  3. There is a queen in column \(j\):\[\sum_{i'} x_{i',j} \ge 1\]
  4. There is a queen in the same diagonal. The diagonal is described by \((i',j')\) such that \(i'-j'=i-j\). So we have: \[\sum_{i',j'|i'-j'=i-j} x_{i',j'}\ge 1\] If you prefer you can write this as \[\sum_{i'|1 \le i'-i+j \le n } x_{i',i'-i+j} \ge 1 \] 
  5. There is a queen in the same anti-diagonal. The anti-diagonal is described by \((i',j')\) such that \(i'+j'=i+j\). So we have: \[\sum_{i',j'|i'+j'=i+j} x_{i',j'}\ge 1\] This can also be written as \[\sum_{i'| 1 \le i+j-i' \le n} x_{i',i+j-i'} \ge 1\]


We can write these conditions in one big constraint. So we can write:

Minimum Dominating Set of Queens Problem
\[\begin{align}\min& \>\color{DarkRed}z=\sum_{i,j} \color{DarkRed} x_{i,j}\\ & \sum_{j'} \color{DarkRed}x_{i,j'} + \sum_{i'} \color{DarkRed}x_{i',j} + \sum_{i',j'|i'-j'=i-j} \color{DarkRed}x_{i',j'} +\sum_{i',j'|i'+j'=i+j} \color{DarkRed}x_{i',j'} \ge 1 && \forall i,j \\ & \color{DarkRed}x_{i,j}\in\{0,1\} \end{align}\]

For an \(8\times 8\) board, we need 5 queens. Here are two solutions:


You can verify that every unoccupied square is under attack.

Note that this formulation actually does a bit of double counting. E.g. when we look at the constraint for cell \((2,3)\) we see:


e(2,3)..  x(1,2) + x(1,3) + x(1,4) + x(2,1) + x(2,2) + 4*x(2,3) + x(2,4)
     
      + x(2,5) + x(2,6) + x(2,7) + x(2,8) + x(3,2) + x(3,3) + x(3,4) + x(4,1)
     
      + x(4,3) + x(4,5) + x(5,3) + x(5,6) + x(6,3) + x(6,7) + x(7,3) + x(7,8)
     
      + x(8,3) =G= 1 ; (LHS = 0, INFES = 1 ****)


We see that x(2,3) has a coefficient 4. This is harmless. However it looks a bit unpolished. With a little bit more careful modeling we can get rid of this coefficient 4. A complicated way would be: \[ \sum_{j'}x_{i,j'} + \sum_{i'|i'\ne i} x_{i',j} + \sum_{i',j'|i'-j'=i-j,i'\ne i, j'\ne j} x_{i',j'} +\sum_{i',j'|i'+j'=i+j,i'\ne i, j'\ne j} x_{i',j'} \ge 1 \>\> \forall i,j\] The first summation includes \(x_{i,j}\) while the other three summations exclude explicitly an occurrence of \(x_{i,j}\). Simpler is just to subtract \(3 x_{i,j}\): \[\sum_{j'} x_{i,j'} + \sum_{i'} x_{i',j} + \sum_{i',j'|i'-j'=i-j} x_{i',j'} +\sum_{i',j'|i'+j'=i+j} x_{i',j'}-3x_{i,j} \ge 1\>\> \forall i,j\] Here we just compensate for the double counting.

Now we see:


e(2,3)..  x(1,2) + x(1,3) + x(1,4) + x(2,1) + x(2,2) + x(2,3) + x(2,4) + x(2,5)
     
      + x(2,6) + x(2,7) + x(2,8) + x(3,2) + x(3,3) + x(3,4) + x(4,1) + x(4,3)
     
      + x(4,5) + x(5,3) + x(5,6) + x(6,3) + x(6,7) + x(7,3) + x(7,8) + x(8,3)

      =G= 1 ; (LHS = 0, INFES = 1 ****)


When we ask: how many different solution are there?, we use again the Cplex solution pool. And again, we have our tolerance problem:


pool.absgapNumber of solutions
02
0.54860

As the objective is integer valued, in some sense an absolute gap tolerance of 0.5 seems the safest. With this we find the correct number of solutions [2]. See [1] for a more in-depth discussion of this tolerance problem.

References


  1. Chess and solution pool, http://yetanothermathprogrammingconsultant.blogspot.com/2018/11/chess-and-solution-pool.html.
  2. Weisstein, Eric W.,  Queens Problem, http://mathworld.wolfram.com/QueensProblem.html
  3. Henning Fernau, minimum dominating set of queens: A trivial programming exercise?, Discrete Applied Mathematics, Volume 158, Issue 4, 28 February 2010, Pages 308-318. This is about programming instead of modeling. The issues are very different.
  4. Saad Alharbi and, Ibrahim Venkat, A Genetic Algorithm Based Approach for Solving the Minimum Dominating Set of Queens Problem, Hindawi Journal of Optimization, Volume 2017. I am not sure why a meta-heuristic is a good choice for solving this problem: you will not find proven optimal solutions.