help-glpk
[Top][All Lists]

## [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

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...
Time used: 60.0 secs.  Memory used: 6.0 Mb.

.
.
.

Time used: 840.0 secs.  Memory used: 16.8 Mb.
Time used: 900.0 secs.  Memory used: 17.3 Mb.
Time used: 960.0 secs.  Memory used: 17.8 Mb.
^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;

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...
+     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

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...
+     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
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

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...
+     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
Model has been successfully processed

glpsol --math axpby.

lt.guess.mathprog
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...
+    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

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...
^C

Which since there is no solution, optimal or not, I assume looking for it will
never stop.

> ----- Original Message -----
> 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: