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.

**Reference**

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

**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). $Offtext Sets 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; Parameters 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; Variables 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 Variables core; Positive Variable line; Equations 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 * this is a very difficult problem that takes a long time with * the default settings. we use an optca value that will * cause termination after finding the best solution, but before * proving that it is the best. the best solution is 4. Option optca = 3.9; Solve cube minimizing num using mip;