[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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>
> Cc: "glpk xypron" <address@hidden>, address@hidden, 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:
Download Opera 9 at http://www.opera.com
Powered by Outblaze