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
```

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.

Keywords: mixed integer linear programming, maximum knights problem, mathematics
\$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);

Equation
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  /
knightx / deftotal, defmovex /;

option optCr = 0, optCa = .999;

solve knight  using mip max total;
solve knightx using 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 - 0.5;

option optCr = 1, optCa = 100, limCol = 0, limRow = 0, solPrint = off;

Set
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;
``````
GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170