[Help-glpk] Solving KenKen problems using CMPL and GLPK

[Nigel Galloway]

Andrew,

Thanks for the link, CMPL is a useful addition to GLPK. Attached is 
kenken903.gen and kenken.rules. If you wish to have an example of 
using glpk with cmpl (which is difficult to do in mathprog) please 
feel free to include them in the glpk examples.

The attached solve the following problem where each row and line 
contain the numbers 1 to 6:

a1-a2=4 or a2-a1 = 4
a3/b3 or b3/a3 = 3
a4*a5*b5*c5 = 300
a6-b6=4 or b6-a6=4
b1+b2+c2=11
b4*c3*c4=48
c1-d1=1 or d1-c1=1
c6-d6=1 or d6-c6=1
d2*e1*e2=10
d3+d4=6
d5*e4*e5=36
e3/f3=2 or f3/e3=2
e6-f6=2 or f6-e6=2
f1-f2=2 or f2-f1=2
f4-f5=5 or f5-f4=5

as follows:

C:\Users\Nigel\COLIOP>cmpl -ff -ikenken903.gen -mkenken903.mps

C:\Users\Nigel\COLIOP>glpsol --freemps --min --output kenken903.sol 
kenken903.mp
s
GLPSOL: GLPK LP/MIP Solver, v4.45
Parameter(s) specified in the command line:
  --freemps --min --output kenken903.sol kenken903.mps
Reading problem data from `kenken903.mps'...
Problem: kenken903.mps
kenken903.mps:379: warning: unable to determine objective row
375 rows, 364 columns, 1548 non-zeros
283 integer variables, 214 of which are binary
1703 records were read
GLPK Integer Optimizer, v4.45
375 rows, 364 columns, 1548 non-zeros
283 integer variables, 214 of which are binary
Preprocessing...
16 constraint coefficient(s) were reduced
301 rows, 214 columns, 938 non-zeros
150 integer variables, 133 of which are binary
Scaling...
  A: min|aij| = 1.000e+000  max|aij| = 2.160e+002  ratio = 2.160e+002
GM: min|aij| = 2.444e-001  max|aij| = 4.091e+000  ratio = 1.674e+001
EQ: min|aij| = 6.106e-002  max|aij| = 1.000e+000  ratio = 1.638e+001
2N: min|aij| = 6.250e-002  max|aij| = 1.500e+000  ratio = 2.400e+001
Constructing initial basis...
Size of triangular part = 266
Solving LP relaxation...
GLPK Simplex Optimizer, v4.45
301 rows, 214 columns, 938 non-zeros
       0: obj =  0.000000000e+000  infeas = 9.838e+001 (35)
*   132: obj =  0.000000000e+000  infeas = 1.558e-015 (17)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+   132: mip =     not found yet >=              -inf        (1; 0)
+   173: >>>>>  0.000000000e+000 >=  0.000000000e+000   0.0% (4; 1)
+   173: mip =  0.000000000e+000 >=     tree is empty   0.0% (0; 9)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.5 Mb (530222 bytes)
Writing MIP solution to `kenken903.sol'...

Producing the following solution:


    123456
    ______

a |263541
b |641235
c |316452
d |425163
e |154326
f !532614

Do you emember the 25x25 Sudoku monster from 2007?

CMPL solves that quite easily (though this can be done in mathprog):

C:\Users\Nigel\COLIOP>cmpl -ff -iSudoku25x25.gen -mSudoku25x25.mps

C:\Users\Nigel\COLIOP>glpsol --freemps --min --output test\TEST.out 
Sudoku25x25.
mps
GLPSOL: GLPK LP/MIP Solver, v4.45
Parameter(s) specified in the command line:
  --freemps --min --output test\TEST.out Sudoku25x25.mps
Reading problem data from `Sudoku25x25.mps'...
Problem: Sudoku25x25.mps
Sudoku25x25.mps:2504: warning: unable to determine objective row
2500 rows, 15625 columns, 62500 non-zeros
15625 integer variables, 1486 of which are binary
50983 records were read
GLPK Integer Optimizer, v4.45
2500 rows, 15625 columns, 62500 non-zeros
15625 integer variables, 1486 of which are binary
Preprocessing...
980 rows, 1228 columns, 4912 non-zeros
1228 integer variables, all of which are binary
Scaling...
  A: min|aij| = 1.000e+000  max|aij| = 1.000e+000  ratio = 1.000e+000
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 701
Solving LP relaxation...
GLPK Simplex Optimizer, v4.45
980 rows, 1228 columns, 4912 non-zeros
       0: obj =  0.000000000e+000  infeas = 5.680e+002 (279)
     500: obj =  0.000000000e+000  infeas = 1.608e+001 (274)
    1000: obj =  0.000000000e+000  infeas = 2.944e-002 (274)
*  1079: obj =  0.000000000e+000  infeas = 7.826e-013 (274)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+  1079: mip =     not found yet >=              -inf        (1; 0)
+ 12626: >>>>>  0.000000000e+000 >=  0.000000000e+000   0.0% (20; 32)
+ 12626: mip =  0.000000000e+000 >=     tree is empty   0.0% (0; 91)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   4.0 secs
Memory used: 8.3 Mb (8673244 bytes)
Writing MIP solution to `test\TEST.out'...

produced:

JNHLGCOSQMWBPEUKYAXFTDRIV
IRWOULDXPKHMVFNQTJBEACSGY
ACDESIGNVHYOTQJRPLMUXFKBW
TYXPKUFJABGRIDSCVHWOLQEMN
MBFVQRYWETXLACKINGSDPOHJU
FJRWOYKMXNBVQGHDUPLICATES
LGINYEACHDSFWUTOXBJMQKVRP
SKTUMPROWFLJYIEAHCQVNGBDX
HPADVTSQBLOCKRXEGFYNMUJWI
EQCXBGUVJIANDPMSWTRKFLYHO
VWJGTSBFRXPDCOLUMNAYIEQKH
RXBSFDPKNJUIEHYVLQTGOMWAC
YAUKDOQILCMWRNBFJEHSVPGXT
QOPCLHMEGYTKFAVWBIDXUJNSR
NHMIEVWATUQXJSGPOKCRYBFLD
CSLMHJNDIPKGUTRXFOVBEWAYQ
WTGRNXVUMOEPBJDHAYKQSICFL
PDQAXWETFRVYHLCGISUJBNMOK
UEYBIKHGSANQOWFTCMPLRXDVJ
OVKFJBLYCQISXMANDREWHTUPG
GLVJPFTBUERHMXWYQDICKSONA
DMNQCAXLKGJUSYOBRVFPWHITE
BUOTRQIHDSFENVPLKWGAJYXCM
XFEYAMCROWDTLKIJSUNHGVPQB
KISHWNJPYVCAGBQMEXOTDRLUF


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

kenken903.gen
Description: Binary data

kenken.rules
Description: Binary data