topic Re: Reading and timing bunches of SUDOKUs in Optmodel in Mathematical Optimization, Discrete-Event Simulation, and OR

Reading and timing bunches of SUDOKUs in Optmodel

ODENWALD — Thu, 07 Jun 2018 15:17:14 GMT

Hi:

Reading and handling one SUDOKU at a time -- no problem.

Now I have lists (e.g. 87 records=lines) one SUDOKU == 1 line - densely packed without spaces.

4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........

The old SAS code for a quadratic SUDOKU data scheme with spaces ::

data SUDOKUS.Most_Difficult_1 ;
input C1-C9;
datalines;
9 . . 8 . . . . .

etc

The old read data in Optmodel ::

read data SUDOKU into [i = _n_] {j in SPALTEN} <SU[i,j] = col("C"||j)> ; /* SPALTEN means COLUMNS */

I'm not aware how the read data has to be modified.

I want to loop within Optmodel over such collections , produce solutions with various solvers and collect all timing information from SAS Log into SAS datasets.

Any suggestions how I best handle the technicalities of reading and time collecting ?

Kind regards, Odenwald

Re: Reading and timing bunches of SUDOKUs in Optmodel

RobPratt — Thu, 07 Jun 2018 20:53:14 GMT

The following code loops over all instances, calling the CLP solver and recording the solution time for each. You could also loop over solvers and record other statistics.

data indata;
   input clues $81.;
   datalines;
4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........
..5..7..1.7..9..3....6.......3..1..5.9..8..2.1..2..4....2..6..9....4..8.8..1..5..
;

proc optmodel printlevel=0;
   set INSTANCES;
   str clues {INSTANCES};
   read data indata into INSTANCES=[_N_] clues;
   set ROWS = 1..9;
   set COLS = ROWS; /* Use an alias for convenience and clarity */
   num c {INSTANCES, ROWS, COLS} init .;
   num k;
   for {instance in INSTANCES} do;
      k = 0;
      for {i in ROWS} do;
         for {j in COLS} do;
            k = k + 1;
            c[instance,i,j] = input(char(clues[instance],k),1.);
         end;
      end;
   end;

   /* Declare variables */
   var X {ROWS, COLS} >= 1 <= 9 integer;

   /* Nine row constraints */
   con RowCon {i in ROWS}:
      alldiff({j in COLS} X[i,j]);

   /* Nine column constraints */
   con ColCon {j in COLS}:
      alldiff({i in ROWS} X[i,j]);

   /* Nine 3x3 block constraints */
   con BlockCon {s in 0..2, t in 0..2}:
      alldiff({i in 3*s+1..3*s+3, j in 3*t+1..3*t+3} X[i,j]);

   /* Fix variables to cell values */
   /* X[i,j] = c[i,j] if c[i,j] is not missing */
   num instance_this;
   con FixCon {i in ROWS, j in COLS: c[instance_this,i,j] ne .}:
      X[i,j] = c[instance_this,i,j];

   num solve_time {INSTANCES};
   for {instance in INSTANCES} do;
      put instance=;
      instance_this = instance;
      solve;
      print X;
      solve_time[instance] = _OROPTMODEL_NUM_['SOLUTION_TIME'];
   end;
   print solve_time;

   create data outdata from [instance] solve_time;
quit;

Re: Reading and timing bunches of SUDOKUs in Optmodel

ODENWALD — Tue, 12 Jun 2018 10:50:55 GMT

Hi Rob :

Super ! Worked technically like a charm.

Could you add some details w.r.t. looping over solvers etc ?

I noted some effects you are probably aware of with the way of setting up the model :

The OPTMODEL presolver is disabled for problems with predicates.

Running 1465 SUDOKUs there was a huge variation (solving time going up to 16, 19, 99! secs and completely effecting the average to the negative ::

on a slow notebook : average = 0.2278 median = 0.016 .

Using the trivariate binary variables approach average(MILP) = 0.013 and average(CLP) = 0.014 over the same set of puzzles.

.................

Thanks again.

Odenwald

Re: Reading and timing bunches of SUDOKUs in Optmodel

RobPratt — Tue, 12 Jun 2018 14:19:15 GMT

Here's an illustration of looping over solvers, say for your binary formulation:

   set SOLVERS = {'clp','milp'};
   num solve_time {INSTANCES, SOLVERS};
   for {instance in INSTANCES} do;
      put instance=;
      instance_this = instance;
      solve with clp;
      solve_time[instance,'clp'] = _OROPTMODEL_NUM_['SOLUTION_TIME'];
      solve with milp;
      solve_time[instance,'milp'] = _OROPTMODEL_NUM_['SOLUTION_TIME'];
   end;

And here's an illustration of looping over algorithms for the same solver, LP in this case:

   set ALGORITHMS = {'ds','ps','ns','ip'};
   num solve_time {INSTANCES, ALGORITHMS};
   for {instance in INSTANCES} do;
      put instance=;
      instance_this = instance;
      for {alg in ALGORITHMS} do;
         solve with lp / algorithm=(alg);
         solve_time[instance,alg] = _OROPTMODEL_NUM_['SOLUTION_TIME'];
      end;
   end;

Can you please provide the data for the slow instances? What SAS/OR version are you using?