But One other Math Programming Marketing consultant: Chess and answer pool

The (n)-queens drawback is a well-liked instance of a “chessboard non-attacking drawback” [1,2]:

• On an (n occasions n) chessboard place as many queens as doable such that none of them is attacked
• Given this, what number of other ways can we place these queens?

We use the standard (8 occasions 8) board.

Rooks

A associated, less complicated drawback is about inserting rooks. The optimization drawback may be very easy: it’s an project drawback:

For an (8 occasions 8) board it’s apparent that the variety of rooks we are able to place is 8. Right here we present two configurations:

We will simply reply: what number of different configuration with 8 rooks can we discover? That is [n! = 8! = 40,320] Principally, we enumerate all row and column permutations of the diagonal depicted above. We will use the answer pool in solvers like Cplex and Gurobi to seek out all of them. Right here I exploit Cplex and the efficiency is phenomenal: all 40,320 options are present in 16 seconds.

Board

Within the fashions on this write-up, I assume a board that has the coordinates:

Coordinate System in Fashions

This additionally signifies that the diagonals:

Foremost diagonal and anti-diagonal

have the shape (i=j) and (i+j=9). Extra usually, for the downward sloping essential diagonals we have now the rule: [i=j+k] for (ok=-6,dots,6). The anti-diagonals will be described as: [i+j=k] for (ok=3,dots,15). We will illustrate this with:

Diagonals and anti-diagonals

The primary image has cell values (a_{i,j}=i-j) and the second has cell values (a_{i,j}=i+j).

Bishops

The mannequin for putting bishops is barely extra sophisticated: we have to verify the primary diagonals and the anti-diagonals. We use the notation from the earlier paragraph. So with this, our mannequin can appear like:

Word that these constraints translate instantly into GAMS:

bishop_main(k1).. sum((i,j)$(v(i)-v(j)=v(k1)),x(i,j)) =l= 1;
bishop_anti(k2).. sum((i,j)$(v(i)+v(j)=v(k2)),x(i,j)) =l= 1;

Two doable options are:

We will accommodate 14 bishops. There are 256 totally different options (in response to Cplex).

Word: the GAMS show of the answer shouldn’t be so helpful:

----     47 VARIABLE x.L  

            1           2           4           5           7           8

1           1                       1           1           1
2           1
3           1                                                           1
6           1                                                           1
7                                                                       1
8           1           1           1           1

For that reason I present the answer utilizing the (LaTeX) chessboard package deal [5]. You have to be conscious that the coordinate system is totally different than what we use within the fashions.

Queens

The (n) queens drawback is now quite simple: we simply want to mix the 2 earlier fashions.

An answer can appear like:

We will place 8 queens and there are 92 options.

Notes:

See Also

My First PCB! – Laura Lindzey

• Cplex delivered 91 options. This appears to be a tolerance subject. I used an answer pool absolute hole of zero (possibility SolnPoolAGap=0 or as it’s known as just lately: mip.pool.absgap=0) [4]. As the target jumps by one, it’s secure to set absolutely the hole to 0.01. With this hole we discovered all 92 options. Is that this a bug? Possibly. Presumably. In all probability. This 92-th answer shouldn’t be alleged to be reduce off. Clearly, poor scaling shouldn’t be a problem right here: this mannequin is as well-scaled as you may get. I believe that the (considerably poorly understood) mixture of tolerances (feasibility, integer, optimality) causes Cplex to behave this fashion. If too many binary variables assume 0.99999 (say inside the integer tolerance) we have now an goal which is simply too small. Certainly, we are able to additionally get to 92 options by setting the integer tolerance epint=0.  Word that setting the integer tolerance to zero will typically enhance answer occasions.
  Typically tolerances “assist” us: they make it simpler to seek out possible or optimum options. Here’s a case after they actually trigger issues.
  In fact this dialogue shouldn’t be an excellent commercial for Blended Integer Programming fashions. Ideally we should always not have to fret about technical particulars comparable to tolerances when constructing and fixing fashions which might be in any other case pretty simple (no big-M’s, well-scaled, small in measurement).
• A two step algorithm may also help to stop the tolerance subject mentioned above:
  1. Clear up the maximization drawback: we discover max variety of queens (z^*).
  2. Create a feasibility drawback with variety of queens equal to (z^*). I.e. we add the constraint: [sum_{i,j} x_{i,j}=z^*] This drawback has no goal. Discover all possible integer options utilizing the answer pool. We need not set an answer pool hole for this.

  On the floor, this seems similar to the tactic above. Nevertheless, bodily having the constraint (sum x_{i,j}=z^*) within the mannequin will be certain that all relaxations obey this constraints. So any binary variables which might be mechanically integer (i.e. near 0 or 1) won’t ever trigger us to deviate an excessive amount of from (z^*). That is delicate.

• Most of the 92 options are the results of easy symmetric operations, comparable to rotating the board, or reflection [2]. The variety of totally different options after ignoring these symmetries is simply 12. The GAMS mannequin in [3] finds these.
• The mannequin in [3] handles the bishop constraints in a different way, by calculating an offset and writing [sum_i x_{i,i +mathit{sh}_s} le 1 >>forall s] I considerably desire our strategy.  

Kings

Kings are dealt with fairly cleverly in [1]. They observe that there can’t be a couple of king in every block [begin{matrix} x_{i,j} & x_{i,j+1} x_{i+1,j} & x_{i+1,j+1}end{matrix}] Word that we solely need to look ahead (and downward) as a earlier block would have coated issues to the left (or above). The mannequin can appear like:

Two options are:

We will place 16 kings, and there are plenty of doable configurations: 281,571 (says Cplex).

Knights

To position knights we arrange a set (mathit{bounce}_{i,j,i’,j’}) indicating if we are able to bounce from cell ((i,j)) to cell ((i’,j’)). We solely must look ahead, so for every ((i,j)) we have to think about 4 circumstances:

Word that close to the border we might have fewer than 4 circumstances. In GAMS we are able to populate the set (mathit{bounce}) straightforwardly:

bounce(i,j,i-2,j+1) = sure;
bounce(i,j,i-1,j+2) = sure;
bounce(i,j,i+1,j+2) = sure;
bounce(i,j,i+2,j+1) = sure;

The mannequin can appear like:

We will place 32 knights. There are solely two totally different options:

Conclusion

The answer pool is a strong device to enumerate probably giant numbers of integer options. Nevertheless, with default tolerances, setting the answer pool absolute hole tolerance to zero might trigger completely good integer options to be missed. That is dicey stuff.

References