Next to the most known methods:

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.

Are there ideas for different methods for solving LPs/literature for other methods? What are their weak points?

asked 19 Feb '16, 19:08

opti100's gravatar image

opti100
9317
accept rate: 0%


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.

You can also take a look at Fourier-Motzkin elimination, but it's an exponential time algorithm and hopelessly slow in practice.

link

answered 21 Feb '16, 12:14

Brian%20Borchers's gravatar image

Brian Borchers
1.3k15
accept rate: 21%

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 http://www.optimization-online.org/DB_FILE/2011/11/3233.pdf)

(22 Feb '16, 10:34) Andreas

If your goal in looking at alternative methods is developing intuition and deepening your understanding, I'd recommend Kipp Martin's Large Scale Linear and Integer Optimization: A Unified Approach, which discusses Fourier-Motzkin and others in terms of projections and immersions, as well as Simplex and Interior Point.

link

answered 23 Feb '16, 19:53

Leo's gravatar image

Leo
1.1k17
accept rate: 8%

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:

  1. The improved simplex method (http://pubsonline.informs.org/doi/pdf/10.1287/ijoc.1100.0425) tries to overcome degeneracy by solving an auxiliary problem.
  2. Criss-cross methods that try to combine primal and dual simplex pivots in one algorithm (https://en.wikipedia.org/wiki/Criss-cross_algorithm )
link

answered 23 Feb '16, 09:43

Philipp%20Christophel's gravatar image

Philipp Chri...
1.0k27
accept rate: 22%

edited 23 Feb '16, 13:10

(26 Feb '16, 16:41) Matthew Salt... ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190

Asked: 19 Feb '16, 19:08

Seen: 573 times

Last updated: 26 Feb '16, 16:41

OR-Exchange! Your site for questions, answers, and announcements about operations research.