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

[Meketon, Marc]

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-----
From: address@hidden [mailto:address@hidden On Behalf Of Andrew Makhorin
Sent: Sunday, March 13, 2011 4:08 AM
To: address@hidden
Subject: [Help-glpk] [Fwd: Manually selecting an initial interior point]

-------- Forwarded Message --------
From: Shiv, Vighnesh <address@hidden>
To: address@hidden <address@hidden>
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
address@hidden
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. 
Thank you for your cooperation.