knights.gms : Maximum Knights Problem

Description

This MIP model finds the maximum number of knights that can be
placed on a board. Two different formulations are presented.
The second formulation is 'tight' and may perform better with certain
MIP codes. Once we found the max number of knights, we solve a series
of MIPs to find ALL solutions.

We will use lags (relative positions) to describe the allowed moves.
The labels H and V indicate horizontal and vertical moves as shown
below:

                 0 0
                0   0
                  X
                0   0
                 0 0


Reference

  • Dudeney, H E, Amusements in Mathematics. Dover, New York, 1970.

Large Model of Type : MIP


Category : GAMS Model library


Main file : knights.gms

$title Maximum Knights Problem (KNIGHTS,SEQ=158)
$Ontext
  This MIP model finds the maximum number of knights that can be
  placed on a board. Two different formulations are presented.
  The second formulation is 'tight' and may perform better with certain
  MIP codes. Once we found the max number of knights, we solve a series
  of MIPs to find ALL solutions.

  We will use lags (relative positions) to describe the allowed moves.
  The labels H and V indicate horizontal and vertical moves as shown
  below:

                   0 0
                  0   0
                    X
                  0   0
                   0 0


Dudeney, H E, Amusements in Mathematics. Dover, New York, 1970.

$Offtext

set  i size of board            /  1*8  /
     n number of possible moves / m1*m8 /;

alias(i,j,k);

table move(*,n)  all possible knight moves

     m1 m2 m3 m4 m5 m6 m7 m8
   H -2 -2 -1 -1 +1 +1 +2 +2
   V -1 +1 -2 +2 -2 +2 -1 +1

variable total; binary variable x(i,j);

equations deftotal         total knights on board
          defmove(i,j)     move restrictions
          defmovex(n,i,j)  move restrictions;

deftotal.. total =e= sum((i,j), x(i,j));

defmove(i,j)..  sum(n, x(i+move('h',n),j+move('v',n))) =l= card(i)*(1-x(i,j));

defmovex(n,i,j)..  x(i+move('h',n),j+move('v',n)) =l= 1-x(i,j);

model knight  / deftotal,defmove  /
model knightx / deftotal,defmovex /

option optcr=0,optca=.999;

solve knight  use mip max total;
solve knightx use mip max total;

* Now we try to see how many different ways are there to arrange
* the same number of knights.

scalar maxknight; maxknight = total.l;
total.lo  = total.l-.5;
option optcr=1,optca=100,limcol=0,limrow=0,solprint=off;


sets ss    max number of solutions groups / seq1*seq20 /
     s(ss) dynamic set for solution groups

parameter cutval all possible solutions for cut generation;

equation cut(ss)  known solutions to be eliminated;

cut(s).. sum((i,j), cutval(s,i,j)*x(i,j)) =l= maxknight-1;

model knight1 / deftotal,defmovex,cut /;

s(ss) = no;
total.lo  = maxknight - .5;
knight1.solvestat = %solvestat.NormalCompletion%;
knight1.modelstat = %modelstat.Optimal%;

loop(ss$(knight1.solvestat=%solvestat.NormalCompletion% and
        (knight1.modelstat=%modelstat.Optimal% or
         knight1.modelstat=%modelstat.IntegerSolution%)),
   s(ss) = yes;
   cutval(ss,i,j) = x.l(i,j);
   solve knight1 maximizing total using mip;  )

option cutval:0:0:1; display cutval;