cube.gms : Three-Dimensional Noughts and Crosses

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

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