[Help-glpk] Solving Hidato problems using CMPL and GLPK.

[Nigel Galloway]

The joy continues. Is there anything one can not do with CMPL and GLPK.

We must get from 1 to 42 passing through the fixed cells in sequence.
-1 indicates that the cell is not used:
 
 x, x,11,12,42, x, x
 8, 6, x, x,16,17, x
 7, x, x,-1, x, x,38
 3, x,-1,-1,-1, x,20
 x, 1,-1,-1,-1, x,36
28,26, x, x, x, x, x
 x, x,30,31,23, x, x

The attached files solve this as follows:

C:\Users\Nigel\COLIOP>cmpl -ff -iHidato.gen -mHidato.mps

C:\Users\Nigel\COLIOP>glpsol --freemps --min --output Hidato.sol Hidato.mps
GLPSOL: GLPK LP/MIP Solver, v4.45
Parameter(s) specified in the command line:
 --freemps --min --output Hidato.sol Hidato.mps
Reading problem data from `Hidato.mps'...
Problem: Hidato.mps
Hidato.mps:1907: warning: unable to determine objective row
1903 rows, 2937 columns, 10454 non-zeros
2435 integer variables, 440 of which are binary
11345 records were read
GLPK Integer Optimizer, v4.45
1903 rows, 2937 columns, 10454 non-zeros
2435 integer variables, 440 of which are binary
Preprocessing...
420 constraint coefficient(s) were reduced
1148 rows, 623 columns, 2938 non-zeros
281 integer variables, 262 of which are binary
Scaling...
 A: min|aij| = 1.000e+000  max|aij| = 4.200e+001  ratio = 4.200e+001
GM: min|aij| = 3.928e-001  max|aij| = 2.546e+000  ratio = 6.481e+000
EQ: min|aij| = 1.543e-001  max|aij| = 1.000e+000  ratio = 6.481e+000
2N: min|aij| = 1.250e-001  max|aij| = 1.625e+000  ratio = 1.300e+001
Constructing initial basis...
Size of triangular part = 1127
Solving LP relaxation...
GLPK Simplex Optimizer, v4.45
1148 rows, 623 columns, 2938 non-zeros
      0: obj =  0.000000000e+000  infeas = 1.918e+002 (21)
*   380: obj =  0.000000000e+000  infeas = 3.053e-014 (1)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+   380: mip =     not found yet >=              -inf        (1; 0)
+  6732: >>>>>  0.000000000e+000 >=  0.000000000e+000   0.0% (14; 658)
+  6732: mip =  0.000000000e+000 >=     tree is empty   0.0% (0; 725)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   4.0 secs
Memory used: 2.1 Mb (2210788 bytes)
Writing MIP solution to `Hidato.sol'...

giving:

09 10 11 12 42 41 40
08 06 13 15 16 17 39
07 05 14    18 19 38
03 04          37 20
02 01          21 36
28 26 25 24 32 22 35
27 29 30 31 23 33 34


-- 
_______________________________________________
Surf the Web in a faster, safer and easier way:
Download Opera 9 at http://www.opera.com

Hidato.rules
Description: Binary data

Hidato.gen
Description: Binary data