Description

White and black balls are to be arranged in a cube one to a
cell in such a way as to minimize the number of lines with balls
of equal color. For this example the length of the cube is three.
a total of 49 lines exist in a cube of 3x3x3. 27 lines by changing
only one coordinate, 18 diagonals within a plane, and 4 diagonals
going across planes.

Small Model of Type : MIP

Category : GAMS Model library

Main file : cube.gms

$title Three-dimensional Noughts and Crosses (CUBE,SEQ=42)

$onText
White and black balls are to be arranged in a cube one to a
cell in such a way as to minimize the number of lines with balls
of equal color. For this example the length of the cube is three.
a total of 49 lines exist in a cube of 3x3x3. 27 lines by changing
only one coordinate, 18 diagonals within a plane, and 4 diagonals
going across planes.


Williams, H P, Experiments in the formulation of Integer Programming
Problems. Mathematical Programming Study 2 (1974).

Keywords: mixed integer linear programming, mathematics, mathematical games,
          noughts and crosses, tic-tac-toe
$offText

Set
   s    'domain for line identification' / a, b, c, incr, decr /
   x(s) 'coordinate labels'              / a, b, c    /
   d(s) 'directions'                     / incr, decr /
   b    'bounds'                         / low, high  /;

Alias (x,y,z), (d,dp), (s,sp,spp);

Set ld(s,sp,spp) 'line definition';
ld("incr",y,z)  = yes;
ld(x,"incr",z)  = yes;
ld(x,y,"incr")  = yes;
ld("incr",d,z)  = yes;
ld(x,"incr",d)  = yes;
ld(d,y,"incr")  = yes;
ld("incr",d,dp) = yes;

display ld;

Parameter
   ls(b)   'sign for line definitions' / low  1, high -1 /
   lr(b)   'rhs for line definitions'  / low  2, high -1 /
   df(x,s) 'line definition function';

df(x,y)      = ord(y) - ord(x);
df(x,"decr") = 1 + card(x) - 2*ord(x);
display df;

Variable
   core(x,y,z)    'placement of balls (white 0 black 1)'
   line(s,sp,spp) 'line identification'
   num            'number of lines of equal color';

Binary   Variable core;
Positive Variable line;

Equation
   nbb              'total number of balls definition'
   ldef(s,sp,spp,b) 'line definitions'
   ndef             'number of lines definition';

nbb..  sum((x,y,z), core(x,y,z)) =e= floor(card(x)**3/2);

ldef(s,sp,spp,b)$ld(s,sp,spp)..
   ls(b)*sum(x, core(x+df(x,s),x+df(x,sp),x+df(x,spp))) =l= line(s,sp,spp) + lr(b);

ndef.. num =e= sum((s,sp,spp)$ld(s,sp,spp), line(s,sp,spp));

Model cube / all /;

$if set nosolve $exit

* note: optCa = 3.9 has been removed due to significant improvements in solver performance
solve cube minimizing num using mip;