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

[Nigel Galloway]

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