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:
[EMAIL PROTECTED]:~/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" <[EMAIL PROTECTED]>
> To: "Nigel Galloway" <[EMAIL PROTECTED]>
> Cc: "glpk xypron" <[EMAIL PROTECTED]>, [EMAIL PROTECTED], [email protected]
> 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
_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
