help-glpk
[Top][All Lists]

## Re: [Help-glpk] Re: Hello,Nigel, I have some questions about GLPK

 From: Nigel Galloway Subject: Re: [Help-glpk] Re: Hello,Nigel, I have some questions about GLPK Date: Sun, 30 Nov 2008 14:17:23 +0100

```Interesting.

The concluding section:

Parametric analysis

This is an option available in some packages and involves automatically
investigating how the solution changes as some parameter is altered. For
example for the LP:

minimise   45 * x1 + 70 * x2
subject to certain constraints

a parametric analysis of the objective function would involve looking at the
LP:

minimise   (45+alpha) * x1 + (70+alpha) * x2
subject to the same constraints

for varying values of alpha and seeing how the optimal solution changes (if
at all) as alpha varies.

If you are working towards solving this LP by crashing on my computer then I
can live with that.

Using glpk prior to 4.33 examples/t1.cs solves this:

address@hidden:~/glpkcontdec\$ mono t1.exe 45 70
a = 45, b = 70
Trying 45
0:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (0)
1:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+     1: mip =     not found yet >=              -inf        (1; 0)
+     3: >>>>>   0.000000000e+00 >=   0.000000000e+00   0.0% (3; 0)
+     3: mip =   0.000000000e+00 >=     tree is empty   0.0% (0; 5)
INTEGER OPTIMAL SOLUTION FOUND
x = -1, y = 1, a*x + b*y = 25
Trying 25
!     3:   objval =   0.000000000e+00   infeas =   0.000000000e+00
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+     3: mip =     not found yet >=              -inf        (1; 0)
+     5: >>>>>   0.000000000e+00 >=   0.000000000e+00   0.0% (3; 0)
+     5: mip =   0.000000000e+00 >=     tree is empty   0.0% (0; 5)
INTEGER OPTIMAL SOLUTION FOUND
x = -3, y = 2, a*x + b*y = 5
Trying 5
Solution is 5

Using the Theorem of Division:

70 = 45 * 1 + 25
45 = 25 * 1 + 20
25 = 20 * 1 + 5
20 = 5  * 4 + 0

therefore the answer is 5.

So we beat the Theorem of Division by two steps, and not an alpha in sight. I
look forward to reviewing a general solution using Parametric Analysis (by
Christmas?).

> ----- Original Message -----
> From: "Andrew Makhorin" <address@hidden>
> To: "Nigel Galloway" <address@hidden>
> Subject: Re: [Help-glpk] Re: Hello,Nigel, I have some questions about GLPK
> Date: Fri, 28 Nov 2008 16:22:55 +0300
>
>
> > I guess 'Crashing...' has a special glpk meaning and
> > isn't as worrying as it is.
>
> Crashing is a technique used to produce a good starting basis for the
> simplex method. The term "crashing" is widely used, not only in glpk;
> see for example: http://people.brunel.ac.uk/~mastjjb/jeb/or/lpadv.html .

>

--
_______________________________________________
Surf the Web in a faster, safer and easier way: