Answers to: Reference for finding optimal LP extreme point in polynomial timehttp://www.or-exchange.com/questions/11324/reference-for-finding-optimal-lp-extreme-point-in-polynomial-time<p>My problem is as follows: given some LP, we can find an optimal solution for it in (weakly) polynomial time via some interior point method. When there are multiple optima, the found solution might not be an extreme point but on the middle of one of the polyhedrons faces.</p>
<p>Now I want to get from there to an optimal extreme point (for example because I have an integral IP formulation and only the extreme points are interesting for me). This should be possible in polynomial time by traversing the current face until hitting some inequality, reducing the dimension of the face by one and repeating until ending on a desired extreme point.</p>
<p>Does anyone know a good reference or a text book where this issue is dealt with? So far I could not find a proper resource even though this argument seems to be relevant when making conclusions of the type: "This problem has an ideal and compact formulation and can therefore be solved in polynomial time"</p>enWed, 11 Feb 2015 22:39:37 -0500Comment by Matthew Saltzman on Matthew Saltzman's answerhttp://www.or-exchange.com/questions/11324/reference-for-finding-optimal-lp-extreme-point-in-polynomial-time#11340<p>Technically, for a proof of polynomial complexity, you really need both steps. The primal-dual method terminates close to--but not necessarily on--the optimal face. Megiddo's work assumes that you know precisely a strictly complementary solution, but at termination of the primal-dual method, you may have some small but nonzero primal/dual variable pairs that need to be complementary. You need to decide that one or the other of those is the true zero, and choosing incorrectly puts you on the wrong face. Ye's and related work shows how to do that in polynomial time.</p>Matthew SaltzmanWed, 11 Feb 2015 22:39:37 -0500http://www.or-exchange.com/questions/11324/reference-for-finding-optimal-lp-extreme-point-in-polynomial-time#11340Comment by FDahms on Matthew Saltzman's answerhttp://www.or-exchange.com/questions/11324/reference-for-finding-optimal-lp-extreme-point-in-polynomial-time#11327<p>Thank you!
2 is exactly what I needed.</p>FDahmsMon, 09 Feb 2015 09:46:28 -0500http://www.or-exchange.com/questions/11324/reference-for-finding-optimal-lp-extreme-point-in-polynomial-time#11327Answer by Matthew Saltzmanhttp://www.or-exchange.com/questions/11324/reference-for-finding-optimal-lp-extreme-point-in-polynomial-time/11326<p>A good starting point is Steven Wright, <em>Primal-Dual Interior-Point Methods</em>, SIAM Press, 1997.</p>
<p>There are two steps to converting an interior-point solution to a basic solution:</p>
<ol>
<li>Project the approximate solution onto the optimal face. (E.g., Yinyu Ye, "On the finite convergence of interior-point algorithms for linear programming," <em>Mathematical Programming 57</em>, 1992 325-335)</li>
<li>Select a basis corresponding to a corner point on the optimal face. (Nimrod Megiddo, "On finding primal and dual optimal bases," <em>ORSA Journal on Computing 3</em>, 1991, 63-65.</li>
</ol>Matthew SaltzmanMon, 09 Feb 2015 09:39:54 -0500http://www.or-exchange.com/questions/11324/reference-for-finding-optimal-lp-extreme-point-in-polynomial-time/11326