2.1.1 Coexisting Armies of Queens (coexx)

Run LPL Code  ,  PDF Document

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 shs be the shift value of a (forward) diagonal relative to the main diagonal, and let rvs,i be the reverse shift order value.

We introduce various binary variables: xwi,j = 1 if cell (i,j) has a white queen; xbi,j = 1 if cell (i,j) has a black queen; wai = 1 if row i contains a white queen; wbj = 1 if column j contains a white queen; wcs = 1 if (forward) diagonal s contains a white queen; wds = 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 (xwi,j is true) then row i and column j must contain a white queen”, that is, wai and wbj 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.)

max   tot
      xwi,j →   wai ∧  wbj      forall i,j ∈ I          (1)
      xw       →  wc            forall s ∈ S, i ∈ I    (2)
         i,i+sh        s
      xwi,i+rvs,i →   wds         forall s ∈ S, i ∈ I    (3)
      xbi,j →   wai  ∧  wbj    forall i,j ∈ I          (4)
      xbi,i+shs →   wcs         forall s ∈ S, i ∈ I    (5)
      xbi,i+rvs,i →  wds         forall s ∈ S, i ∈ I    (6)
            ∑
      tot =    xbi,j                                  (7)
            i∑,j
      tot =    xwi,j                                  (8)
            i,j

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:

xwi,j →   wai  ∧ wbj    forall i,j ∈ I

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

(xwi,j ∨  wai ) ∧ (xwi,j  ∨  wbj)   forall i,j ∈ I

And then to two constraints as follows:

1 - xwi,j + wai ≥  1  ,  1 - xwi,j + wbj ≥ 1   forall i,j ∈ I

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


PIC

Figure 1: 2 × 9 Queens can be placed maximally

...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;