Three-Dimensional Noughts and Crosses: A Combinatorial Problem

PROC OPTMODEL Statements and Output

The first several PROC OPTMODEL statements declare parameters and index sets and then read the input data:

proc optmodel;
   num n = &n;
   set CELLS = 1..n cross 1..n cross 1..n;

   set COLORS;
   num num_balls {COLORS};
   read data color_data into COLORS=[_N_] num_balls;

The following statements declare the IsColor variables and the first two families of constraints:

   var IsColor {CELLS, COLORS} binary;
   con IsColor_con {<i,j,k> in CELLS}:
      sum {color in COLORS} IsColor[i,j,k,color] = 1;
   con Num_balls_con {color in COLORS}:
      sum {<i,j,k> in CELLS} IsColor[i,j,k,color] = num_balls[color];

The following statements declare the IsMonochromatic variables and the objective:

   num num_lines init 0;
   set LINES = 1..num_lines;
   var IsMonochromatic {LINES} binary;

   min NumMonochromaticLines = sum {line in LINES} IsMonochromatic[line];

The following SET statement declares (but does not populate) an index set that will contain the cells for each line:

   set <num,num,num> CELLS_line {LINES};

The following FOR loops use the SETOF operator to populate CELLS_line for each row:

   for {i in 1..n, j in 1..n} do;
      num_lines = num_lines + 1;
      CELLS_line[num_lines] = setof {k in 1..n} <i,j,k>;
   end;
   for {i in 1..n, k in 1..n} do;
      num_lines = num_lines + 1;
      CELLS_line[num_lines] = setof {j in 1..n} <i,j,k>;
   end;
   for {j in 1..n, k in 1..n} do;
      num_lines = num_lines + 1;
      CELLS_line[num_lines] = setof {i in 1..n} <i,j,k>;
   end;

The following FOR loops use the SETOF operator to populate CELLS_line for each face diagonal:

   for {i in 1..n} do;
      num_lines = num_lines + 1;
      CELLS_line[num_lines] = setof {j in 1..n} <i,j,j>;
      num_lines = num_lines + 1;
      CELLS_line[num_lines] = setof {j in 1..n} <i,j,n+1-j>;
   end;
   for {j in 1..n} do;
      num_lines = num_lines + 1;
      CELLS_line[num_lines] = setof {i in 1..n} <i,j,i>;
      num_lines = num_lines + 1;
      CELLS_line[num_lines] = setof {i in 1..n} <i,j,n+1-i>;
   end;
   for {k in 1..n} do;
      num_lines = num_lines + 1;
      CELLS_line[num_lines] = setof {i in 1..n} <i,i,k>;
      num_lines = num_lines + 1;
      CELLS_line[num_lines] = setof {i in 1..n} <i,n+1-i,k>;
   end;

The following statements use the SETOF operator to populate CELLS_line for each cube diagonal:

   num_lines = num_lines + 1;
   CELLS_line[num_lines] = setof {t in 1..n} <t,t,t>;
   num_lines = num_lines + 1;
   CELLS_line[num_lines] = setof {t in 1..n} <t,t,n+1-t>;
   num_lines = num_lines + 1;
   CELLS_line[num_lines] = setof {t in 1..n} <t,n+1-t,t>;
   num_lines = num_lines + 1;
   CELLS_line[num_lines] = setof {t in 1..n} <t,n+1-t,n+1-t>;

The following PUT statements demonstrate that num_lines is $((n+2)^3 - n^3) / 2$ , which is 49 when $n = 3$ .

   put num_lines=;
   put (((n+2)^3 - n^3) / 2)=;

The following CON statement enforces the rule that if all cells in a line are the same color, then $\Variable{IsMonochromatic[line]} = 1$ :

   con Link_con {line in LINES, color in COLORS}:
      sum {<i,j,k> in CELLS_line[line]} IsColor[i,j,k,color]
    - card(CELLS_line[line]) + 1
   <= IsMonochromatic[line];

The following statements call the mixed integer linear programming solver and use the .sol variable suffix to populate assigned_color[i,j,k]:

   solve;
   num assigned_color {CELLS};
   for {<i,j,k> in CELLS} do;
      for {color in COLORS: IsColor[i,j,k,color].sol > 0.5} do;
         assigned_color[i,j,k] = color;
         leave;
      end;
   end;

The following statements print the values of assigned_color[i,j,k] for each i and display in the log which cells make up each monochromatic line:

   for {i in 1..n}
      print {j in 1..n, k in 1..n} assigned_color[i,j,k];
   for {line in LINES: IsMonochromatic[line].sol > 0.5}
      put CELLS_line[line]=;

By default, the PUT statement writes to the log. You can use the following FILE statement to redirect log output to the listing:

   file print;
   for {line in LINES: IsMonochromatic[line].sol > 0.5}
      put CELLS_line[line]=;
quit;

Figure 17.2 shows the output from the mixed integer linear programming solver.

Figure 17.2: Output from Mixed Integer Linear Programming Solver

The OPTMODEL Procedure

Problem Summary
Objective Sense	Minimization
Objective Function	NumMonochromaticLines
Objective Type	Linear

Number of Variables	103
Bounded Above	0
Bounded Below	0
Bounded Below and Above	103
Free	0
Fixed	0
Binary	103
Integer	0

Number of Constraints	127
Linear LE (<=)	98
Linear EQ (=)	29
Linear GE (>=)	0
Linear Range	0

Constraint Coefficients	500

Performance Information
Execution Mode	Single-Machine
Number of Threads	1

Solution Summary
Solver	MILP
Algorithm	Branch and Cut
Objective Function	NumMonochromaticLines
Solution Status	Optimal
Objective Value	4

Relative Gap	0
Absolute Gap	0
Primal Infeasibility	0
Bound Infeasibility	0
Integer Infeasibility	0

Best Bound	4
Nodes	523
Iterations	6034
Presolve Time	0.00
Solution Time	0.16

assigned_color
	1	2	3
1	2	2	1
2	1	1	2
3	2	2	1

assigned_color
	1	2	3
1	1	2	2
2	2	1	2
3	1	1	2

assigned_color
	1	2	3
1	2	1	1
2	1	2	2
3	2	1	1

Figure 17.3 shows the output from the PUT statement.

Figure 17.3: Output from PUT Statement

                             The OPTMODEL Procedure                             
                                                                                
CELLS_line[15]={<2,1,3>,<2,2,3>,<2,3,3>}                                        
CELLS_line[24]={<1,2,3>,<2,2,3>,<3,2,3>}                                        
CELLS_line[40]={<1,1,1>,<2,2,1>,<3,3,1>}                                        
CELLS_line[41]={<1,3,1>,<2,2,1>,<3,1,1>}