7
$\begingroup$

I am trying to find some real life ("non trivial") examples of Linear Programming.

So far, most of the examples that I come across are from introductory textbooks involving some basic example about farmers choosing between different crops to grow based on expected harvest and market price; or some similar example of a factory in which two different machines manufacture different types of items at different speeds, and again based on expected consumer demand, the manager at the factory is expected to decide how much of each machine's workload should be assigned to which type of item. Sometimes, there might be some constraints that need to be taken into consideration. Generally, these problems I come across can be solved using algebraic manipulation or through linear programming.

I posted an example of one of these problems below:

enter image description here

Although these types of problems are great examples to familiarize one's self with Linear Programming, the context of these problems generally appear as "too simple", and instantly one begins to think that these are big oversimplifications of real world problems and such oversimplified problems do not fully represent the complexities that are usually encountered in the real world. I am trying to look for some examples of Linear Programming problems in more realistic situations.

We are usually told that the real world is often characterized by non-linear relationships; apart from a stepping stone to learn about optimization and more complicated concepts, are there still instances in which pure Linear Programming problems still arise in the real world?

Can someone please suggest some more realistic examples of (purely) Linear Programming problems that arise in the real world?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
11
$\begingroup$

Anecdotally, the first industrial purchasers of mainframe computers were petroleum producers who need the mainframes to solve linear programming models used to schedule refinery operations. I believe LPs are still used in refinery scheduling. McKinsey "Energy Insights" has a nice web page with pertinent information.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ (+1) for specific industry example and McKinsey link $\endgroup$
    – SecretAgentMan
    Feb 9, 2022 at 17:09
  • $\begingroup$ @ prubin: thank you so much for your answer! I am surprised that these problems didnt have non linear components? $\endgroup$
    – stats_noob
    Feb 9, 2022 at 17:17
  • $\begingroup$ Some of them are probably feedstock problems, basically mixture problems, which are usually linear as long as the ingredients don't react with each other. Also, bear in mind that it is not uncommon to approximate nonlinear models with linear ones, trading off a (hopefully small) reduction in accuracy for a (hopefully large) improvement in solvability. $\endgroup$
    – prubin ♦
    Feb 9, 2022 at 19:53
  • 1
    $\begingroup$ I am working with a giant oil company right now that wants to up their LP game for deciding what products to choose. They all use this, although frequently the LP is just one of many steps (but one of the most important ones) in creating the model and finding an answer. The other steps are mostly about the fact that nothing in life is truly linear. Anecdotally Valero is one of the best. $\endgroup$
    – Mike Wise
    Feb 10, 2022 at 16:01
7
$\begingroup$

Starting with a Real-life applications side note: I would assume this to be true for many domains, but when you're working on OR/Analytics/Data Science related projects, one of the very essential skills to have would be 'to connect the dots'. Be it a client-facing company or a company where you're building an in-house product, you'll hardly come across a situation where you'll specifically be told to use a particular algorithm or meta-heuristic. Most of the time you'll have to 'own' the problem and come up with ways to solve it. So whether to use Linear programming or not may boil down to the problem solver i.e. You!

Now coming back to your question: Yes, there are many areas where Linear Programming can still be pretty useful. If I am adding MILP in the mix, then the potential is huge but even without that, you will have a choice to use LP. Even I did something a few months back with LP. I was solving a special variant of Facility Location Problem, where we were looking to add one warehouse in the network as there was a surge in the customer demand. Not going much deep into how we did it, we implemented a heuristic alongside a Linear Programming equation. We solved that with lpsolve in R, then even made a dashboard of it.

When you will start working you'll also face similar situations where you can implement LP. The key will be how you'll 'connect the dots'.

Improve this answer
$\endgroup$
2
$\begingroup$

There are many real world applications that specialize the transportation problem which may be framed as an LP. Beyond the many problems that can be framed directly in terms of the transportation problem, there are also those that use it as an important step of an algorithm. For instance in my masters, I show that the stochastic stacker crane problem, a generalization of the traveling salesman problem, has an almost surely linear time $(1+\epsilon)$-competitive algorithm. A crucial step is finding a good approximate solution to the Euclidean Bipartite Matching Problem by solving the transportation problem on clusters of nearby points.

Improve this answer
$\endgroup$

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.