Just a LP, really?

In recent talks in scientific conferences, I saw some people dissmiss pure linear programming (LP) models as being easy and primitive. I often got said “oh, that’s just a LP”. Linear programming is put in the box of solved problems, like some network problems such as the (pure) shortest path or max flow. In fact, I think that quite the opposite is true. For many reasons, LP is still an important area of research and deserves much interest.

For one, solving LPs very efficiently is very important to solve mixed-integer linear (MILP) models. Solver developers have found many clever ways of solving difficult MILPs while limiting the number of nodes that need to be explored, but branching and solving LPs is still very much needed. My main body of research is in supply chain planning, where models tend to become very large very quickly.

Second, LP in itself is very appropriate to model several real-world planning or control problems. For instance, the Quebec province’s office of the chief forester needs to solve several LPs to determine the maximum annual volume of wood that can be cut for each of the province’s 70+ management areas. Some of these models are quite large (say, 5 million variables and 1 million constraints), and the amount of sensitivity analysis they can perform is therefore limited if each LP takes several hours to solve.

For these reasons it is my belief that research efforts must continue on how to better solve LPs.

Speak Your Mind