Problem

Two armies of queens (black and white) peacefully coexist on a chessboard when they are placed on the board in such a way that no two queens from opposing armies can attack each other. The problem is to find the maximum two equal-sized armies. This model is from the GAMS model library (GAMS SEQ=218). See also [10].

Modeling Steps

The model is a tighter formulation of the model coex. The chessboard is a 8 × 8 grid,
defining i ∈ I = {1,…, 8} rows and j ∈ I columns. It contains s ∈ S = {1,…, 2|I|- 3} diagonals.
Let sh_{s} be the shift value of a (forward) diagonal relative to the main diagonal, and let rv_{s,i} be
the reverse shift order value.

We introduce various binary variables: xw_{i,j} = 1 if cell (i,j) has a white queen; xb_{i,j} = 1 if
cell (i,j) has a black queen; wa_{i} = 1 if row i contains a white queen; wb_{j} = 1 if column j
contains a white queen; wc_{s} = 1 if (forward) diagonal s contains a white queen; wd_{s} = 1 if
(backward) diagonal s contains a white queen. Furthermore, let us introduce the total number
of white (black) queens as an integer variable tot.

Constraints (1-6) are formulated in a logical way. Basically, these constraints say the following:
if a cell occupies a white queen then in the same row, column and the two diagonals only white
queens are allowed, and if a cell occupies a black queen then no white queen is allowed in the
same row, column and the two diagonals. Constraint (1), for instance, formulates the
following fact: “if cell (i,j) is occupied by a white queen (xw_{i,j} is true) then row i and
column j must contain a white queen”, that is, wa_{i} and wb_{j} both must be true. The
other logical constraints can be interpreted in a similar way (try to verbalize them
yourself!).

Contraints (7-8) define the total number of white and black queens and the objective function maximized that number. (In addition, we fix the position of one queen in the LPL code, since this does not change the optimal value.)

Further Comments

The model is a typical model with logical constraints. LPL translates these constraints automatically into linear integer constraints (for more information see my Logical Paper). For instance, take the first constraint:

First it is transformed to a CNF-form (conjunctive normal form) as follows:

And then to two constraints as follows:

In GAMS, these constraints must be translated manually to mathematical linear constraints. GAMS has this very handy Alias syntax to specify several names for one index (In LPL, it can be placed directly in the declaration of the sets). This unimpressive feature is helpful for large and complicated models, no other language contains it. GAMS has a somewhat “old-fashioned” syntax like =g= for ≥. One also needs to declare an equation first, and only after that the constraint expression can be assigned. Comments are not clearly marked or separated from the formal syntax.

Note also, GAMS is – apart from some output statements – a purely declarative language and, therefore, has no instruction to generate graphs.

LPL code (run coexx)

model COEXX "Coexisting Armies of Queens";

set i,j := 1..8 "size of chess board";

s := 1..2*#i-3 "diagonal offset";

parameter sh{s} := s-#i+1 "diag shift values";

rv{s,i} := #i+1-2*i+ sh "reverse shift order";

binary variable xw{i,j} "has a white queen";

xb{i,j} "has a black queen";

wa{i} "white in row i";

wb{i} "white in column j";

wc{s} "white in diagonal s";

wd{s} "white in backward diagonal s";

variable tot;

constraint

aw{i,j}: xw -> wa[i] and wb[j]

"white in row i/col j";

cw{s,i}: xw[i,i+sh] -> wc[s] "white in diag s";

dw{s,i}: xw[i,i+rv] -> wd[s] "white in back diag s";

ab{i,j}: xb -> ~wa[i] and ~wb[j] "black in row i/col j";

cb{s,i}: xb[i,i+sh] -> ~wc[s] "black in diag s";

db{s,i}: xb[i,i+rv] -> ~wd[s] "black in back diag s";

eb: tot = sum{i,j} xb "total black";

ew: tot = sum{i,j} xw "total white";

fx11: xb[1,1] = 1; --fix one queen in the NW corner

maximize obj: tot;

// draw the solution blackboard

Draw.Scale(50,50);

{i,j} Draw.Rect(i,j,1,1,if((i+j)%2,0,1),0);

{i,j|xb} Draw.Circle(j+.5,i+.5,.3,5);

{i,j|xw} Draw.Circle(j+.5,i+.5,.3,4);

end

GAMS code (download coexx.gms)

Sets i size of chess board / 1* 8 /

s diagonal offsets / 1* 13 /

scalar idiags correct size of s;

idiags = 2*card(i) - 3;

abort$(card(s) <> idiags) 's has incorrects size',idiags;

Alias (i,j)

Parameter sh(s) shift values for diagonals

rev(s,i) reverse shift order;

sh(s) = ord(s) - card(i) + 1 ;

rev(s,i) = card(i) + 1 - 2*ord(i) + sh(s);

Binary Variable xw(i,j) has a white queen

xb(i,j) has a black queen

wa(i) white in row i

wb(i) white in column j

wc(s) white in diagonal s

wd(s) white in backward diagonal s;

Variable tot;

Equations aw(i,j) white in row i

bw(j,i) white in column j

cw(s,i) white in diagonal s

dw(s,i) white in backward diagonal s

ew total white

ab(i,j) black in row i

bb(j,i) black in column j

cb(s,i) black in diagonal s

db(s,i) black in backward diagonal s

eb total black;

aw(i,j).. wa(i) =g= xw(i,j);

bw(j,i).. wb(j) =g= xw(i,j);

cw(s,i).. wc(s) =g= xw(i,i+sh(s));

dw(s,i).. wd(s) =g= xw(i,i+rev(s,i));

Solution output of the LPL drawing code

...continue with GAMS code

ab(i,j).. 1-wa(i) =g= xb(i,j);

bb(j,i).. 1-wb(j) =g= xb(i,j);

cb(s,i).. 1-wc(s) =g= xb(i,i+sh(s));

db(s,i).. 1-wd(s) =g= xb(i,i+rev(s,i));

eb.. tot =e= sum((i,j), xb(i,j));

ew.. tot =e= sum((i,j), xw(i,j));

Model army / all /;

option limcol=0,limrow=0;

xb.fx('1','1') = 1; ! fix one position in the NW corner

Solve army maximizing tot using mip;