GAMS [ Home | Support | Sales | Solvers | Documentation | Model Libraries | Search | Contact Us ]

knights.gms : Maximum Knights Problem

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:
Large Model of Type: MIP
$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;