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: [email protected] [mailto:[email protected]] On Behalf Of Andrew Makhorin Sent: Sunday, March 13, 2011 4:08 AM To: [email protected] Subject: [Help-glpk] [Fwd: Manually selecting an initial interior point] -------- Forwarded Message -------- From: Shiv, Vighnesh <[email protected]> To: [email protected] <[email protected]> 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 [email protected] 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. _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
