help-glpk
[Top][All Lists]

## RE: [Help-glpk] [Fwd: Manually selecting an initial interior point]

 From: Meketon, Marc Subject: RE: [Help-glpk] [Fwd: Manually selecting an initial interior point] Date: Sun, 13 Mar 2011 19:02:01 -0500

```Most experiments that people have made on trying to "warm-start" an interior
point algorithm have failed.  That is, starting an interior point algorithm at
a close-to-optimal solution does not seem to work well - usually because the
point is too close to a "wall" and the interior point algorithms get blocked by
it.

In 2008 Jacek Gondzio publish "A New Unblocking Technique to Warmstart Interior
Point Methods Based on Sensitivity Analysis" in which he claimed some positive
results, but it would take some work to implement his refinements to the
interior point algorithm.

In your particular case, you mentioned that you did not have a basic solution.
But were there any zero's at all in the solution (more generally, were any of
the variables at their lower or upper bounds)?  If so, then you would not have
a true interior point solution and any warm-start approach would not work.

My knowledge is probably too old, but I believe that some linear programming
solvers have the ability to "crash" a basis when using the simplex algorithm:
conceptually, using other information to develop the first basis.  In your
case, it would be nice to, say, pick the largest or most significant of your
variables in your initial solution and use them to tell the solver to start
with those columns when forming the first basis.  Maybe some other GLPK user
would know how to "crash" a basis.

-Marc

-----Original Message-----
Sent: Sunday, March 13, 2011 4:08 AM
Subject: [Help-glpk] [Fwd: Manually selecting an initial interior point]

-------- Forwarded Message --------
Subject: Manually selecting an initial interior point
Date: Sat, 12 Mar 2011 21:38:45 -0800

Hello,

I have a linear program for which I know a feasible solution close to the
optimal solution. This feasible solution isn't basic, however, so I don't think
I can use it as an initial basis for the simplex algorithm. Is it possible for
me to set this feasible solution as an initial point for GLPK's interior-point
method? If not, is there some other way I could use my known feasible solution
to more efficiently solve my linear program?

Thank you very much in advance!
V

_______________________________________________
Help-glpk mailing list
http://lists.gnu.org/mailman/listinfo/help-glpk

This e-mail and any attachments may be confidential or legally privileged. If
you received this message in error or are not the intended recipient, you
should destroy the e-mail message and any attachments or copies, and you are
prohibited from retaining, distributing, disclosing or using any information
contained herein.  Please inform us of the erroneous delivery by return e-mail.