help-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Help-glpk] Re: For complexity size isn't the issue (The case of the mis


From: Nigel Galloway
Subject: [Help-glpk] Re: For complexity size isn't the issue (The case of the missing 12).
Date: Fri, 4 Jul 2008 12:43:42 +0100

True, I could use some method to determine smallest multiple of
the largest common divisor, say EuclidÂ’s 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: address@hidden
> To: address@hidden
> 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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]