Answers to: Alternative Methods for Solving LPshttp://www.or-exchange.com/questions/13395/alternative-methods-for-solving-lps<p>Next to the most known methods:</p>
<p>Ellipsoid Method, which has theoretical the best property but has big numerical problems.
Barrier Method, which also runs in poly-time, but lacks warm-start for MIPS.
Primal/Dual Simplex Method, which is theoretical worse, but in practice good. </p>
<p>Are there ideas for different methods for solving LPs/literature for other methods?
What are their weak points?</p>enTue, 23 Feb 2016 19:53:28 -0500Answer by Leohttp://www.or-exchange.com/questions/13395/alternative-methods-for-solving-lps/13400<p>If your goal in looking at alternative methods is developing intuition and deepening your understanding, I'd recommend Kipp Martin's <a href="http://www.springer.com/us/book/9780792382027">Large Scale Linear and Integer Optimization: A Unified Approach</a>, which discusses Fourier-Motzkin and others in terms of projections and immersions, as well as Simplex and Interior Point.</p>LeoTue, 23 Feb 2016 19:53:28 -0500http://www.or-exchange.com/questions/13395/alternative-methods-for-solving-lps/13400Answer by Philipp Christophelhttp://www.or-exchange.com/questions/13395/alternative-methods-for-solving-lps/13399<p>There is some research in other ways to solve LPs were "other" does not mean fundamentally different but building on what is already known to find a better way to do things. Two areas come to mind:</p>
<ol>
<li>The improved simplex method (<a href="http://pubsonline.informs.org/doi/pdf/10.1287/ijoc.1100.0425)">http://pubsonline.informs.org/doi/pdf/10.1287/ijoc.1100.0425)</a> tries to overcome degeneracy by solving an auxiliary problem.</li>
<li>Criss-cross methods that try to combine primal and dual simplex pivots in one algorithm (<a href="https://en.wikipedia.org/wiki/Criss-cross_algorithm">https://en.wikipedia.org/wiki/Criss-cross_algorithm</a> )</li>
</ol>Philipp ChristophelTue, 23 Feb 2016 09:43:12 -0500http://www.or-exchange.com/questions/13395/alternative-methods-for-solving-lps/13399Answer by Brian Borchershttp://www.or-exchange.com/questions/13395/alternative-methods-for-solving-lps/13397<p>You can solve LP's using a variety of general purpose convex optimization methods (projected (sub)gradient descent, bundle methods, etc.) However, these kinds of approaches aren't going to be faster in theory or in practice than an interior point method or simplex.<br>
</p>
<p>You can also take a look at Fourier-Motzkin elimination, but it's an exponential time algorithm and hopelessly slow in practice.<br>
</p>Brian BorchersSun, 21 Feb 2016 12:14:18 -0500http://www.or-exchange.com/questions/13395/alternative-methods-for-solving-lps/13397