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

[Nigel Galloway]

Attached are the rules and data for Sudoku 25x25. You are free to use them, and 
the KenKen example, in your manual.

> ----- Original Message -----
> From: "Prof. Dr. Mike Steglich" <address@hidden>
> To: Nigel Galloway <address@hidden>
> Cc: Andrew Makhorin <address@hidden>, Thomas Schleiff <address@hidden>
> Subject: Re: [Help-glpk] Solving KenKen problems using CMPL and GLPK
> Date: Tue, 25 Jan 2011 17:50:46 +0100
>
>
> Hello Nigel,
>
> Thank you for sending your kenken model. Could  you send me the 
> also the Sudoku25x25 model.
>
> It is absolutely interesting to see models from other people 
> within the community. We (Tomas Schleiff and I) are collecting 
> mathematical models written in CMPL. Can I use your example(s) 
> for the CMPL manual?
>
> All the best
>
> Mike
>
>
>
> Am 25.01.2011 um 15:26 schrieb 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><kenken.rules>_______________________________________________
> > Help-glpk mailing list
> > address@hidden
> > http://lists.gnu.org/mailman/listinfo/help-glpk

>


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

Sudoku25x25.gen
Description: Binary data

Sudoku25x25.rules
Description: Binary data