15
$\begingroup$

Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances). As the authors write:

Arguably, the most important consequences of our reductions are constraints on algorithms to solve the LP relaxations. Leaving runtime aside, they show that such algorithms cannot be arbitrarily simple since they must be able to solve any linear program.

Linear programming is an important tool used to solve integer linear programs (via the LP-based branch and bound approach). There has been a huge progress towards solving such integer programs. However, there does not seem to be much progress in solving the general linear programming problem. As far as I know, the classical simplex algorithm or its dual variant is still used in modern IP solvers (even as the default LP algorithm).

Are there are any new algorithms that could potentially beat the simplex algorithm in practice (at least on average)? If not, then I am wondering why?

The result of Průša and Werner implies that no matter how good the underlying formulation is (or no matter how good the valid inequalities can be), we still need to solve the resulting linear program (i.e., ANY linear program) efficiently to be able to solve large problems.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

The simple answer is that for large scale problems (1m+ rows and columns) we would use interior point instead of dual simplex.

The main challenge is not really the solving algorithm, since interior point has polynomial complexity for LP, it's the implementation challenges, i.e., manipulating matrices that take up massive memory (and sometimes need to be cached into the hard drive or distributed among numerous machines), as well as numerical stability and factorising the coefficient matrix which are prone to large scale difficulties.

Improve this answer
$\endgroup$
9
  • 2
    $\begingroup$ Not sure whether your comment about finding an interior point is non-polynomial ist a correct. Do you have some source for that claim. $\endgroup$
    – JakobS
    Aug 23, 2019 at 18:21
  • 2
    $\begingroup$ I also doubt that claim, and I would appreciate some source. @nikaza makes a similar claim in this answer. $\endgroup$
    – Kevin Dalmeijer
    Aug 23, 2019 at 18:27
  • 2
    $\begingroup$ @nikaza In Khachiyan (1980) it is proven that "determining the compatibility of a system of linear inequalities in $\mathbb{R}^n$ belongs to the class of $P$ of problems". This seems to contradict that finding a feasible point is difficult. $\endgroup$
    – Kevin Dalmeijer
    Aug 23, 2019 at 21:50
  • 5
    $\begingroup$ @nikaza The Ellipsoid method of Khachiyan provides a feasible point (or concludes the polytope is empty) in polynomial time. But there is no guarantee the provided point is an integer point. Determining whether a feasible integer point exists in a polytope is NP-complete. Be aware that LP and ILP are very different problems! Also, be aware that if you can optimize an LP, you can also find a feasible solution, using a trick called the Two-Phase method. This involves adding artificial variables to your model that provide you with a known feasible solution. $\endgroup$
    – Paul Bouman
    Aug 24, 2019 at 12:52
  • 1
    $\begingroup$ @JakobS This really needs more space so I started a question to get to the bottom of this. $\endgroup$
    – Nikos Kazazakis
    Aug 27, 2019 at 0:56
3
$\begingroup$

You are right that the dual simplex (and to some degree the primal simplex) are still very much state-of-the-art ways to solve LPs. The last 3 decades saw significant improvements on these algorithms but their main advantage remains warmstarting capabilities. Inside MILP solvers we need to solve many closely related problems and dual simplex (and in some cases primal simplex) excel at doing that.

The interior point method lacks warmstarting but has the major advantage that for large problems it can be threaded fairly efficiently. Simplex algorithms in most cases gain very little from using parallel computing, which in the MIP solver setting is not that much of a problem.

"New" methods for solving LPs I am aware of (and currently remember) are the following:

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks, so an important reason why dual/primal simplex are used in MILP solvers is because of their ability to facilitate warmstarting and solving a sequence of linear programs more efficiently. Hmm. I think if Interior point methods can utilize the power of parallel computing then they would play an important role in solving linear programs in the near future. $\endgroup$
    – rasul
    Aug 27, 2019 at 6:41
  • 1
    $\begingroup$ Interior point methods already play an important role in solving linear programs, as long as they are really linear programs and not part of solving a mixed integer program. As pointed out by others before, IPMs are typically the fastest on large LP problems that you want to solve from scratch. But that is not always the case, the simplex methods have the advantage that you can "guess" the optimal basis and be done right away. IPM always needs to do a certain amount of iterations. Even the primal simplex is sometimes better than the others, especially if there are many more rows than columns. $\endgroup$
    – Philipp Christophel
    Aug 27, 2019 at 7:23
  • $\begingroup$ Good point. I have a linear program that has around $50\times10^6$ non-negative variables and $125\times10^9$ constraints. This is just one linear program and it is not LP-relaxation of a MILP. Is there any way to solve this problem in a reasonable time? I am wondering if the multi threading of the interior point method is handled by GUROBI, CPLEX or any MILP solver automatically? If not, what is your suggestion for solving this linear program? Do you think column generation is suitable? The problem does not have any sort of special structure. $\endgroup$
    – rasul
    Aug 28, 2019 at 2:57
  • $\begingroup$ Just to add further details. I tried to solve a relaxation of this LP with a very small number of constraints and variables. It seems that GUROBI can solve small instances of the primal problem with "dual simplex" and the dual problem with "primal simplex". Either of these is the fastest way to solve small relaxations. When I increase the problem size to 50,000 variables and 10,000,000 constraints, I see a message "killed" and nothing is returned. Similar thing happens when I use CPLEX. $\endgroup$
    – rasul
    Aug 28, 2019 at 3:51
  • $\begingroup$ Linux may kill processes if it is running out of memory. I bet you are running low of memory. $\endgroup$
    – ErlingMOSEK
    Aug 28, 2019 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.