True, I could use some method to determine smallest multiple of the largest common divisor, say Euclids Algorithm, but that is rather what I want GLPK to do.
Note that if I want to do that then I just need to replace a*x + b*y >= 1; with a*x + b*y = the gcd; The minimize is then optional, and no cutting is required. The range in which to minimize can be reduced: param a, integer; param b, integer; var x, integer; var y, integer; s1: min(a,b)-1 >= a*x + b*y >= 1; minimize s: a*x+b*y; solve; printf "%i %i\n",x,y; data; param a := 15; param b := 35; end; --but the result is the same. glpsol --math gcd.mathprog Reading model section from gcd.mathprog... Reading data section from gcd.mathprog... 18 lines were read Generating s1... Generating s... Model has been successfully generated glp_simplex: original LP has 2 rows, 2 columns, 4 non-zeros Objective value = 1 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... + 0: mip = not found yet >= -inf (1; 0) + 5742: mip = not found yet >= 1.000000000e+00 (6456; 0) + 8489: mip = not found yet >= 1.000000000e+00 (9203; 0) + 10565: mip = not found yet >= 1.000000000e+00 (11279; 0) + 12305: mip = not found yet >= 1.000000000e+00 (13019; 0) + 13804: mip = not found yet >= 1.000000000e+00 (14518; 0) + 15133: mip = not found yet >= 1.000000000e+00 (15847; 0) + 16295: mip = not found yet >= 1.000000000e+00 (17009; 0) + 17319: mip = not found yet >= 1.000000000e+00 (18033; 0) + 18229: mip = not found yet >= 1.000000000e+00 (18943; 0) + 19058: mip = not found yet >= 1.000000000e+00 (19772; 0) + 19822: mip = not found yet >= 1.000000000e+00 (20536; 0) + 20538: mip = not found yet >= 1.000000000e+00 (21252; 0) Time used: 60.0 secs. Memory used: 6.0 Mb. + 21211: mip = not found yet >= 1.000000000e+00 (21925; 0) + 21849: mip = not found yet >= 1.000000000e+00 (22563; 0) . . . + 61982: mip = not found yet >= 9.999999999e-01 (62696; 0) Time used: 840.0 secs. Memory used: 16.8 Mb. + 62148: mip = not found yet >= 9.999999999e-01 (62862; 0) + 62314: mip = not found yet >= 9.999999999e-01 (63028; 0) + 62479: mip = not found yet >= 9.999999999e-01 (63193; 0) + 62644: mip = not found yet >= 9.999999999e-01 (63358; 0) + 62809: mip = not found yet >= 9.999999999e-01 (63523; 0) + 62973: mip = not found yet >= 9.999999999e-01 (63687; 0) + 63137: mip = not found yet >= 9.999999999e-01 (63851; 0) + 63300: mip = not found yet >= 9.999999999e-01 (64014; 0) + 63463: mip = not found yet >= 9.999999999e-01 (64177; 0) + 63625: mip = not found yet >= 9.999999999e-01 (64339; 0) + 63786: mip = not found yet >= 9.999999999e-01 (64500; 0) + 63947: mip = not found yet >= 9.999999999e-01 (64661; 0) Time used: 900.0 secs. Memory used: 17.3 Mb. + 64108: mip = not found yet >= 9.999999999e-01 (64822; 0) + 64268: mip = not found yet >= 9.999999999e-01 (64982; 0) + 64428: mip = not found yet >= 9.999999999e-01 (65142; 0) + 64587: mip = not found yet >= 9.999999999e-01 (65301; 0) + 64747: mip = not found yet >= 9.999999999e-01 (65461; 0) + 64905: mip = not found yet >= 9.999999999e-01 (65619; 0) + 65064: mip = not found yet >= 9.999999999e-01 (65778; 0) + 65221: mip = not found yet >= 9.999999999e-01 (65935; 0) + 65379: mip = not found yet >= 9.999999999e-01 (66093; 0) + 65536: mip = not found yet >= 9.999999999e-01 (66250; 0) + 65692: mip = not found yet >= 9.999999999e-01 (66406; 0) + 65848: mip = not found yet >= 9.999999999e-01 (66562; 0) Time used: 960.0 secs. Memory used: 17.8 Mb. + 66004: mip = not found yet >= 9.999999999e-01 (66718; 0) + 66159: mip = not found yet >= 9.999999999e-01 (66873; 0) ^C When the minimize is removed: param a, integer; param b, integer; var x, integer; var y, integer; s1: min(a,b)-1 >= a*x + b*y >= 1; /* minimize s: a*x+b*y; */ solve; printf "%i %i\n",x,y; data; param a := 15; param b := 35; end; Reading model section from gcd.mathprog... Reading data section from gcd.mathprog... 18 lines were read Generating s1... Model has been successfully generated glp_simplex: original LP has 1 row, 2 columns, 2 non-zeros Objective value = 0 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... + 0: mip = not found yet >= -inf (1; 0) + 2: >>>>> 0.000000000e+00 >= 0.000000000e+00 0.0% (3; 0) + 2: mip = 0.000000000e+00 >= tree is empty 0.0% (0; 5) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.1 Mb (104365 bytes) -2 1 Model has been successfully processed which in this case is a correct solution, but isn't always. I used this approach see in a C# program: http://lists.gnu.org/archive/html/help-glpk/2008-02/msg00065.html The same idea implemented in mathprog is: param a, integer; param b, integer; param guess; var x, integer; var y, integer; s1: 1 <= a*x+b*y <= guess; solve; param g := a*x + b*y; param ga := a mod g; param gb := b mod g; param sol := if ga = 0 and gb = 0 then g else g-1; printf "guess = %i\n",guess; printf "x = %i, y = %i, a*x + b*y = %i\n",x,y,g; printf "%s %i\n",if ga = 0 and gb = 0 then "Solution is " else "Not found try ",sol; data; param a := 2424; param b := 772; param guess := 771; end; glpsol --math axpby.lt.guess.mathprog Reading model section from axpby.lt.guess.mathprog... Reading data section from axpby.lt.guess.mathprog... 27 lines were read Generating s1... Model has been successfully generated glp_simplex: original LP has 1 row, 2 columns, 2 non-zeros Objective value = 0 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... + 0: mip = not found yet >= -inf (1; 0) + 4: >>>>> 0.000000000e+00 >= 0.000000000e+00 0.0% (4; 1) + 4: mip = 0.000000000e+00 >= tree is empty 0.0% (0; 9) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.1 Mb (104376 bytes) guess = 771 x = 1, y = -3, a*x + b*y = 108 Not found try 107 Model has been successfully processed Now if guess could be passed to glpsol as a parameter we could make the guess a parameter (or if we could have recursive mathprog), but otherwise making the changes to guess in a text editor we can proceed: glpsol --math axpby.lt.guess.mathprog Reading model section from axpby.lt.guess.mathprog... Reading data section from axpby.lt.guess.mathprog... 27 lines were read Generating s1... Model has been successfully generated glp_simplex: original LP has 1 row, 2 columns, 2 non-zeros Objective value = 0 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... + 0: mip = not found yet >= -inf (1; 0) + 4: >>>>> 0.000000000e+00 >= 0.000000000e+00 0.0% (3; 3) + 4: mip = 0.000000000e+00 >= tree is empty 0.0% (0; 11) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.1 Mb (104376 bytes) guess = 107 x = -7, y = 22, a*x + b*y = 16 Not found try 15 Model has been successfully processed glpsol --math axpby. lt.guess.mathprog Reading model section from axpby.lt.guess.mathprog... Reading data section from axpby.lt.guess.mathprog... 27 lines were read Generating s1... Model has been successfully generated glp_simplex: original LP has 1 row, 2 columns, 2 non-zeros Objective value = 0 OPTIMAL SOLUTION FOUND BY LP PRESOLVER Integer optimization begins... + 0: mip = not found yet >= -inf (1; 0) + 14: >>>>> 0.000000000e+00 >= 0.000000000e+00 0.0% (5; 11) + 14: mip = 0.000000000e+00 >= tree is empty 0.0% (0; 31) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.1 Mb (104376 bytes) guess = 15 x = -50, y = 157, a*x + b*y = 4 Solution is 4 Model has been successfully processed This compares with Euclid's Algorithm where the sequence would be 772, 108, 16, 12, 4. So this program is not just Euclid's Algorith in disguise because GLPK misses the 12. Now if I try a guess of 3, there is no combination of x and y which produce a solution but: glpsol --nopresol --math axpby.lt.guess.mathprog Reading model section from axpby.lt.guess.mathprog... Reading data section from axpby.lt.guess.mathprog... 27 lines were read Generating s1... Model has been successfully generated lpx_adv_basis: size of triangular part = 1 ! 0: objval = 0.000000000e+00 infeas = 0.000000000e+00 OPTIMAL SOLUTION FOUND Integer optimization begins... + 0: mip = not found yet >= -inf (1; 0) + 11168: mip = not found yet >= 0.000000000e+00 (5663; 0) + 16446: mip = not found yet >= 0.000000000e+00 (8302; 0) + 20422: mip = not found yet >= 0.000000000e+00 (10290; 0) + 23730: mip = not found yet >= 0.000000000e+00 (11944; 0) + 26624: mip = not found yet >= 0.000000000e+00 (13391; 0) + 29148: mip = not found yet >= 0.000000000e+00 (14653; 0) + 31314: mip = not found yet >= 0.000000000e+00 (15736; 0) + 33140: mip = not found yet >= 0.000000000e+00 (16649; 0) + 34734: mip = not found yet >= 0.000000000e+00 (17446; 0) + 36150: mip = not found yet >= 0.000000000e+00 (18154; 0) ^C Which since there is no solution, optimal or not, I assume looking for it will never stop. > ----- Original Message ----- > From: [EMAIL PROTECTED] > To: [EMAIL PROTECTED] > Subject: Re: For complexity size isn't the issue. > Date: Mon, 30 Jun 2008 15:11:22 -0700 > > > Hello Nigel! > > The search space is infinite with x, y in [-inf, +inf] with > infinitely many global optimum solutions hence solution time for > branch and bound will be infinite too. > > The optimum is the smallest multiple of > the largest common divisor of a and b > > = the right hand side of st1. > > Obviously the objective function will always be integer. Hence it > would make sense to let the branch and bound add an extra cut > limiting the objective function to the best found solution minus > one. > > Together with a cut providing a correct lower limit this would let > the search stop at the first optimum solution. > > Best regards > > Xypron > -- _______________________________________________ Surf the Web in a faster, safer and easier way: Download Opera 9 at http://www.opera.com Powered by Outblaze _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
