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>enFri, 26 Feb 2016 16:41:41 -0500Comment by Matthew Saltzman on Philipp Christophel's answerhttp://www.or-exchange.com/questions/13395/alternative-methods-for-solving-lps#13407<p>A fairly comprehensive survey of algorithm engineering for the simplex method is this book by Maros: <a href="http://www.amazon.com/Computational-Techniques-International-Operations-Management/dp/1402073321/ref=sr_1_1?ie=UTF8&qid=1456522791&sr=8-1&keywords=maros+simplex">http://www.amazon.com/Computational-Techniques-International-Operations-Management/dp/1402073321/ref=sr_1_1?ie=UTF8&qid=1456522791&sr=8-1&keywords=maros+simplex</a></p>Matthew SaltzmanFri, 26 Feb 2016 16:41:41 -0500http://www.or-exchange.com/questions/13395/alternative-methods-for-solving-lps#13407Answer 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/13399Comment by Andreas on Brian Borchers's answerhttp://www.or-exchange.com/questions/13395/alternative-methods-for-solving-lps#13398<p>I believe for some large-scale LPs these classic methods may not always be the best, so there is a lot of research on using first-order methods to solve these problems (one example is <a href="http://www.optimization-online.org/DB_FILE/2011/11/3233.pdf)">http://www.optimization-online.org/DB_FILE/2011/11/3233.pdf)</a></p>AndreasMon, 22 Feb 2016 10:34:30 -0500http://www.or-exchange.com/questions/13395/alternative-methods-for-solving-lps#13398Answer 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