19
$\begingroup$

Based on the plethora of advancements in optimization algorithms and computer technology that has occurred in the past 50 years - is Linear Programming today as "Powerful" and "Indispensable" as it was in the past?

Are there still some problems that can only be solved using Linear Programming Methods? Do we continue to teach and learn about Linear Programming for only for it's historical importance and basis/introduction to help in understanding modern optimization methods (e.g. "a stepping stone") - or is that in certain types of problems, methods from Linear Programming style display some "attractive theoretical properties" (e.g. convergence), even in the face of modern optimization methods such as Quasi-Newton Methods, Stochastic Gradient Descent and Evolutionary Algorithms?

Even today, are there some problems that can be ONLY solved using methods from Linear Programming?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Would you please, a bit more elaborate on "can be ONLY solved using methods from Linear Programming"? And also, do you mean by linear programming is LP or MILP? $\endgroup$
    – A.Omidi
    Jan 26, 2022 at 13:02
  • $\begingroup$ Linear programming is good for finding a solution maximum in a problem space. Computers allow us to use a LOT of dimensions in the problem space and have much more complex solutions. $\endgroup$
    – Thorbjørn Ravn Andersen
    Jan 29, 2022 at 11:13

2 Answers 2

Reset to default
33
$\begingroup$

Linear Programming is probably more useful than 50 years ago.

The software for solving linear programming problems has dramatically improved and more and more practical problems can be solved. Most of these practical problems are mixed integer linear programs (MILPs), but linear programming is integral to solving MILPs.

To support this statement, here a few indicators:

The airline industry heavily uses mathematical optimization for solving problems such as pairing optimization and crew scheduling. The same is true for public transport. The existence of companies like Sabre and Optibus testifies to that.

The best way to find provably optimal solutions to the traveling salesman problems is based on linear programming: https://www.math.uwaterloo.ca/tsp/concorde.html.

Companies that focus on mathematical optimization with linear programming at their core are thriving, for example Gurobi. Meanwhile, new competitor enter the market for mathematical optimization, specifically linear programming using the simplex algorithm, such as COPT, MindOpt, and Huawei.

Google has increased interest in linear and integer programming, including having their own linear programming solver GLOP.

Amazon is looking for people with skills in linear optimization: https://www.amazon.jobs/de/jobs/1716646/research-scientist.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @ Phillipp: Thank you so much for your answer! When I asked this question, what I had in mind was the following: real world problems are often NON LINEAR - if this is the case, can LINEAR programming be as useful as it originally was, given that many NON LINEAR methods now exist? Thank you so much! $\endgroup$
    – stats_noob
    Feb 15, 2022 at 17:00
  • 1
    $\begingroup$ While it is probably true that most practical problems are non-linear (especially if you consider integrality as a form of non-linear), it is a lot easier to solve linear problems. Many practical problems can be modelled as linear without loosing too much (or anything really) and methods to solve non-linear problems frequently use linear solvers within. Bottom line, linear programming is and will be very important. $\endgroup$
    – Philipp Christophel
    Feb 15, 2022 at 19:31
6
$\begingroup$

There was very big progress in commercial solvers like cplex or gurobi over last 30 years. So there are problems that were not solvable before but can be solved today.

On other side especially in integer domain we can use direct alternatives like sat or constraint solvers that can solve same problem with different approaches. Sat solvers use often learning, constraint solvers have greater expresivity of a model and very powerful global constraints. There are actually problem domains like scheduling where LP/MIP solvers aren't competitive with the alternatives.

Related to your mentioned optimization methods I can talk only about evolutionary algorithms. From my experience they are not performance comparable in solvable problems with a lot of constraints.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ My low view of LP maybe due to have worked on scheduling systems. One requirement change and they stop being solvable with LP, yet customers expect to be able to change requirements. $\endgroup$
    – Ian Ringrose
    Jan 26, 2022 at 23:57
  • 7
    $\begingroup$ LP ≠ MIP. LPs are not as erratic. Also, MIPs give often very good solutions when stopped early. $\endgroup$
    – Erwin Kalvelagen
    Jan 27, 2022 at 0:48
  • $\begingroup$ Good solutions when stopped early ? With MIP there’s sometimes problem to find first feasible solution. It seems to me that MIP solvers are lost when simplex method navigates them to wrong part of search space. $\endgroup$
    – gregy4
    Jan 27, 2022 at 8:09
  • 5
    $\begingroup$ Yes, sometimes. MIPs give often very good solutions when stopped early. I.e. not always. $\endgroup$
    – Erwin Kalvelagen
    Jan 27, 2022 at 10:56
  • $\begingroup$ Thank you so much for your replies! When I asked this question, what I had in mind was the following: real world problems are often NON LINEAR - if this is the case, can LINEAR programming be as useful as it originally was, given that many NON LINEAR methods now exist? Thank you so much! $\endgroup$
    – stats_noob
    Feb 15, 2022 at 17:00

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.