N-queens and solution pool

In [1], I described some chess-related problems. Here, I want to reproduce the \(n\)-queens problem. The single solution problem, placing as many queens on the chess board as possible so they don't attack each other, is pretty standard. I want to focus on the more complex question: How many different ways can we place those queens? In other words: what are all the optimal solutions? We can do this by adding a no-good constraint that forbids the previously found solution. However, as this problem has more than a handful of different solutions, I want to use the Cplex solution pool.

Single Solution Model

We define the decision variables as: \[\color{darkred}x_{i,j} = \begin{cases} 1 & \text{if we place a queen on the square $(i,j)$} \\ 0 & \text{otherwise}\end{cases}\] 

Chess Board

To make sure the queens we place on the board are not attacked, we can only place zero or one queen on

• a row
• a column
• a diagonal
• an anti-diagonal

The row and column constraints are rather obvious: \[\begin{align} & \sum_j \color{darkred}x_{i,j} \le 1 & \forall i \\ & \sum_i \color{darkred}x_{i,j} \le 1 & \forall j \end{align}\] The main diagonal is formed by the squares \((i,j)\) with \(i-j=0\). All 13 diagonals can be described as: \[i-j=k, k\in \{-6,\dots,6\}\] The main anti-diagonal has: \(i+j=9\) and all 13 anti-diagonals can be identified with \[i+j=k, k\in \{3,\dots,15\}\] So the diagonal and anti-diagonal constraints can be written as: \[\begin{align}&\sum_{i,j|i-j=k} \color{darkred}x_{i,j}\le 1 & \forall k \in \{-6,\dots,6\} \\ & \sum_{i,j|i+j=k} \color{darkred}x_{i,j}\le 1 & \forall k \in \{3,\dots,15\}   \end{align}\] Our complete model can look like: 

n-Queens Problem
\[\begin{align} \max & \sum_{i,j}\color{darkred}x_{i,j} \\ & \sum_j \color{darkred}x_{i,j} \le 1 & \forall i \\ & \sum_i \color{darkred}x_{i,j} \le 1 & \forall j \\ & \sum_{i,j|i-j=k} \color{darkred}x_{i,j}\le 1 & \forall k \in \{-6,\dots,6\} \\ & \sum_{i,j|i+j=k} \color{darkred}x_{i,j}\le 1 & \forall k \in \{3,\dots,15\} \\ & \color{darkred}x_{i,j} \in \{0,1\} \end{align}\]

A solution can be:

Visualization

Solutions are visualized using HTML and SVG (Scalable Vector Graphics). This is very easy to use and debug (we can look at the generated HTML file: it is pure text). 

It looks a bit better than the GAMS listing file:

----     73 VARIABLE x.L  placement of queens

            a           b           c           d           e           f           g           h

8                                   1
7                                                                                               1
6                                               1
5                                                                                   1
4           1
3                                                                       1
2                       1
1                                                           1

The Queen piece is just a Unicode character: ♕ (U+2655) [4].

Enumerate all solutions

We can enumerate all optimal solutions with the Cplex solution pool. This yields 92 solutions:

The solution pool algorithm is very fast. It generates all 92 solutions basically instantaneously (0.047 seconds on my machine). 

The solution pool has quite a few options. Here, we focus on option SolnPoolAGap. This means: if an integer solution is within this quantity from the best solution, it is added to the pool. When I use the combination SolnPoolAGap=0 and Threads=1,  I only get 91 solutions. Obviously, the thread count is not the real issue. The underlying problem is likely to be the gap. In MIP modeling, we can write a constraint like \(x=1\) because there are all kinds of (feasibility) tolerances in play. If these tolerances were not there, many models would be infeasible. My conjecture is that the underlying algorithm for the solution pool has a bit of a tolerance problem that sometimes pops up. Somewhere in the code, a "+tol" is missing. One easy fix is to use SolnPoolAGap=0.1 in the model. This is quite safe as the objective \[\max \> \sum_{i,j}\color{darkred}x_{i,j}\] is integer-valued. Another fix, for this particular model, would be to drop the objective and introduce the constraint \[\sum_{i,j}\color{darkred}x_{i,j}=8\] Now we just have a feasibility problem (no objective), and the gap (relative or absolute) has no meaning.

It is noted that the Cplex documentation says [2]:

So, here, they explicitly say to use SolnPoolAGap=0. My claim is that this makes it possible to miss solutions. This also means we really are talking about a Cplex bug here: it does not work as advertised.

Discussion

In [3], a discussion is taking place about this Cplex problem of cutting off a solution (and reporting 91 instead of 92 solutions). Let me give my (highly opinionated) replies.

This is the Cplex page about numerical issues.

I don't buy this. Our model is numerically very benign — about as well-scaled as you can get. We should not have to tinker with feasibility tolerances. Note that setting the integer feasibility tolerance (epint) to 0 will actually help. But this just indicates that Cplex has some tolerance issues in their solution pool algorithm.

"The author is losing solutions because Cplex does smart branching." This is nonsense, in my opinion. So, if I had used "dumb branching" (whatever that means), would things have improved? Note that the Cplex documentation has no option for selecting or unselecting "smart branching." That term is never used. Implementing a custom branching strategy for this model is, of course, for the birds. 

Actually, using strong branching in the varsel option helps! But that is by accident: the solver follows a different solution path. This is the same as increasing the thread count: it helps but has nothing to do with the underlying problem. Choosing a different branching approach is purely a question of performance, not a way to prevent perfectly good solutions from being cut off.

I believe this comment is largely gobbledegook. Where do they learn this stuff?

I have no clue what is being said here. 

Conclusions

It is not very difficult for Cplex to enumerate all 92 possible ways we can place 8 queens on the chess board without them threatening each other. In some cases, Cplex will report 91 solutions. We have discussed some easy workarounds. This leads us to the recommendation not to use a zero gap (contradicting the Cplex documentation). 

HTML and SVG are demonstrated to be simple tools for effective visualizations.

References

1. Chess and solution pool, https://yetanothermathprogrammingconsultant.blogspot.com/2018/11/chess-and-solution-pool.html
2. How to enumerate all solutions. https://www.ibm.com/docs/en/icos/22.1.1?topic=solutions-how-enumerate-all
3. https://news.ycombinator.com/item?id=37738088
4. https://www.compart.com/en/unicode/U+2655

Appendix: GAMS model

$onText     n-queens problem with Cplex solution pool   we should get 92 solutions      with Cplex options threads=1 and SolnPoolAGap=0   we find 91 solutions (instead of 92)      Erwin Kalvelagen   erwin@amsopt.com   $offtext     *-------------------------------------------------------------------- * basic sets *--------------------------------------------------------------------   Sets   i      'rows' /8*1/   j      'columns' /a*h/   kd     'diagonals have i-j=k for k=-6..6' /'-6'*'-1',0*6/   kad    'anti-diagonals have i+j=k for k=3..15' /3*15/ ;   *-------------------------------------------------------------------- * describe diagonals and anti-diagonals *--------------------------------------------------------------------   sets    diag(i,j,kd) 'diagonals'    antidiag(i,j,kad) 'anti-diagonals' ; diag(i,j,kd) = i.val - ord(j) = kd.val; antidiag(i,j,kad) = i.val + ord(j) = kad.val;   option diag:0:0:8, antidiag:0:0:8; display diag, antidiag;   *-------------------------------------------------------------------- * model *--------------------------------------------------------------------   binary variable x(i,j) 'placement of queens'; variable numqueens 'number of queens we can place';   equations    obj               "objective: place as many queens as we can"    row(i)            "don't place two queens in same row"    column(j)         "don't place two queens in same column"    diagonal(kd)      "don't place two queens on the same diagonal"    antidiagonal(kad) "don't place two queens on the same anti-diagonal" ;   obj..       numqueens =e= sum((i,j),x(i,j));   row(i)..    sum(j, x(i,j)) =l= 1; column(j).. sum(i, x(i,j)) =l= 1;   diagonal(kd).. sum(diag(i,j,kd),x(i,j)) =l= 1; antidiagonal(kad).. sum(antidiag(i,j,kad),x(i,j)) =l= 1;   model queens /all/;   *-------------------------------------------------------------------- * find a single solution *--------------------------------------------------------------------   option mip=cplex; solve queens maximizing numqueens using mip;   option numqueens:0,x:0; display "----- Single Solution --------------------",          numqueens.l,x.l         "------------------------------------------"; ;   *-------------------------------------------------------------------- * find all solutions using the Cplex solution pool * note: threads=1 and SolnPoolAGap=0 gives 91 solutions (instead of 92) *--------------------------------------------------------------------   $set gdx allsols.gdx   $onecho > cplex.opt SolnPoolAGap=0.1 solnpoolintensity=4 solnpoolpop=2 populatelim=100000 solnpoolmerge=%gdx%   *to reproduce Cplex tolerance issue use: *SolnPoolAGap=0 *threads=1 $offecho   queens.optfile=1; solve queens maximizing numqueens using mip;   * if all is ok we'll see: * --- Dumping 92 solutions from the solution pool...   *-------------------------------------------------------------------- * load all solutions *--------------------------------------------------------------------   Sets    index0'register elements' /soln_queens_p1*soln_queens_p100/    index(index0)  ;   parameter allsols(index0,i,j);   execute_load "%gdx%" index,allsols=x; display index;     *-------------------------------------------------------------------- * plot all solutions *--------------------------------------------------------------------   $set html allsolutions.html   scalar    tablecolnum 'column counter' /1/    solnum      'solution counter' /1/    posx        'x position'    posy        'y position'    iswhite     'square is white if i+j=even' ;     file f /%html%/; put f;   put '<h1>n-Queens Problem</h1>'/; put '<p>Place as many queens as possible on a standard 8×8 chess board such that they '     "don't attack each other. Show all possible optimal solutions.</p>"/;     put '<table>'/; put '<tr>'/;   loop(index,    put '<td>'/;    put '<svg height="200" width="250" viewbox="0 0 9 9">'/;   * *  column headers (a,b,c,...) *      loop(i,       posy = 0.5+ord(i);       put '<text x="0.5" y="',posy:0:1,             '" dominant-baseline="middle" text-anchor="middle" stroke="black" stroke-width="0.01" fill="black" font-size="1">',             i.tl:0:0,             '</text>'/;    );   * *  row labels (8,7,6,...) *       loop(j,       posx = 0.5+ord(j);       put '<text x="',posx:0:1,             '" y="0.5" dominant-baseline="middle" text-anchor="middle" stroke="black" stroke-width="0.01" fill="black" font-size="1">',             j.tl:0:0,             '</text>'/;    );     * *  black/white board *  black squares are painted light blue *      loop((i,j),      iswhite = (ord(i)+ord(j))/2 <> floor((ord(i)+ord(j))/2);      put '<rect x="',ord(j):0:0,'" y="',ord(i):0:0,'" width="1" height="1" ';      put$(iswhite=1) 'fill="white" ';      put$(iswhite=0) 'fill="lightblue" ';      put 'stroke-width="0.01" stroke="black" />'/;    );      loop((i,j)$(allsols(index,i,j)>0.5),       posx = 0.5+ord(j);       posy = 0.9+ord(i);       put '<text x="',posx:0:1,'" y="',posy:0:1,'" '             'text-anchor="middle" stroke="black" '             'stroke-width="0.01" fill="black" font-size="1">♕</text>'/;                                  );         put '</svg><br><div style="text-align: center;">Solution:',solnum:0:0,' of ',card(index):0:0,'</div></td>'/;      if (tablecolnum=8 and solnum<card(index),       tablecolnum = 0;       put '</tr><tr>'/;    );    tablecolnum=tablecolnum+1;    solnum=solnum+1; ); put '</tr></table>'/;   putclose;     executetool 'win32.ShellExecute "%html%"';