Resources

Three-Dimensional Noughts and Crosses (mpex17)

/***************************************************************/
/*                                                             */
/*          S A S   S A M P L E   L I B R A R Y                */
/*                                                             */
/*    NAME: mpex17                                             */
/*   TITLE: Three-Dimensional Noughts and Crosses (mpex17)     */
/* PRODUCT: OR                                                 */
/*  SYSTEM: ALL                                                */
/*   PROCS: OPTMODEL                                           */
/*    DATA:                                                    */
/*                                                             */
/* SUPPORT:                             UPDATE:                */
/*     REF:                                                    */
/*    MISC: Example 17 from the Mathematical Programming       */
/*          Examples book.                                     */
/*                                                             */
/***************************************************************/


data color_data;
   input num_balls;
   datalines;
13
14
;

%let n = 3;

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;

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

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

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

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

   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;

   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;

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

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

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

   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;

   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]=;

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