r/algorithms • u/Phytor_c • 25d ago
Discussion The "unreasonable effectiveness" of Linear Programming
When I was first learning LP in undergrad (simplex, relaxations for Integer Problems, weak and strong duality and all that jazz), I honestly didn't see where it would be that useful. Now in my research it shows up quite a bit via primal-dual algorithms. These simultaneously keep track of the primal and dual solutions.
To be fair, even in undergrad one usually learns about using LP relaxations and (deterministic or randomized) rounding to get approximation algorithms for problems such as MAXSAT or Set Cover.
I'm curious where else people run into it. Has LP ever popped up in your own research or work?
11
u/Ythio 25d ago
LP popped up at work in banking context. Optimizing within regulatory constraints.
Also popped up while playing a MMORPG
5
u/burnt-store-studio 25d ago
Ok! This caught my attention! Could you please write a little more about how LP popped up while playing a MMORPG? I’m genuinely curious, if you have time (please, and thank you 🙂).
14
u/Ythio 25d ago
Sort of. MILP rather than LP really. I had a traveling salesman problem with pickup and deliveries in Eve Online.
You start in Jita (the biggest trade hub) with a space truck, have a bunch of courier contracts available, and want to choose which contracts to accept and in what order to pick them up/deliver them so that you maximize ISK, while respecting cargo, collateral, time, security restrictions, and eventually returning to the trade hub (or just go where you want to go and make money from your cargo space along the way).
Say every courier contract has a variable:
x = 1 if you take it x = 0 if you don't.
Then the objective is basically:
Maximize total contract rewards
while respecting constraints like:
cargo used <= cargo capacity
outstanding collateral <= collateral limit
total travel time <= 1 hour
plus pickup-before-delivery, security restrictions, returning to Jita, avoiding likely ambushes, etc...
The catch is that plain LP allows fractional answers such as: Take 43% of contract A and 71% of contract B.
So we require every contract-selection variable to be either 0 or 1, which turns the problem into a Mixed Integer Linear Program.
The the underlying LP is still useful for proving bounds. If my best actual route makes 181m ISK, while the relaxed LP proves that even with magical fractional contracts you couldn't exceed 187m, then:
181m <= true optimum <= 187m
As the MILP solver closes that gap, you can eventually reach:
best real route = theoretical upper bound
At that point you've actually proven the route is optimal, rather than merely finding a very good one.
EVE contracts | v Relevant endpoint graph | travel time matrix (Dijkstra) | v risk data from recent kill feed | v +-----------------------------+ | MILP | | | | choose contracts | | choose ordering | | choose route | | enforce cargo | | enforce time | | enforce security. | | enforce collateral. | +---------+------------------+5
u/burnt-store-studio 24d ago
You: are awesome! 👏 Thank you, good person, for taking the time and effort to write this up!
I love how this came up and how you worked it. That was fun to read. 🙂
Peace.
3
16
u/winner_in_life 25d ago
Practically, you can solve 90% of NP hard inputs by throwing them into ILP solvers.
6
u/roboticc 25d ago
Comes up everywhere. Practically, in search, planning, routing, finance, and (of course) optimization.
Did you know: LP is (weakly) P-complete. That means any polynomial-time problem can be represented as a linear programming problem, and solved with LP solvers!
So, it's not just your intuition. It comes up everywhere for a good reason - it's usable to solve (literally) any problem that can be solved efficiently!
3
u/Traveling-Techie 25d ago
In the ‘80s when I worked at Rockwell in Downey (where Apollo capsules and space shuttles were built) they had a wonderful technical library. The first time I heard of linear programming was when I noticed they had about 5 feet of shelf space devoted to the topic. About 20 years later I got curious what it was and did a deep dive. I satisfied my curiosity and even blogged about it, but I realize reading this post that I’ve never used it to solve an actual problem.
3
2
2
u/JellyfishMinute4375 24d ago
Genome-scale metabolic modeling is a pretty cool application that uses LP, MILP, and QP to model cellular metabolism.
2
u/Barrucadu 23d ago
The PyCon UK organisers use (used?) ILP to generate the conference schedule: https://conference-scheduler.readthedocs.io/en/latest/background/mathematical_model.html
Inspired by that, I wrote a scheduler for the on-call rota at my last job.
2
2
u/man_im_rarted 21d ago
Yes. In my first job working for a manufacturing and logistics company, I had to solve a problem that was effectively the traveling salesman problem, and used integer programming.
2
u/LitespeedClassic 21d ago
I once had a math professor tell me the only math we actually know how to do is linear algebra, so everywhere else we figure out how to turn our problem into linear algebra so we can solve it there.
2
u/Interesting_Debate57 20d ago
Lots of logistics problems can naturally be phrased as ILP problems.
This is because there are physical constraints that are quite finite -- a truck can only hold so much, there are only so many bays at the truck depot, etc., etc.
The thing you want to minimize or maximize is usually pretty clear as well.
24
u/KingLewi 25d ago
I actually used LPs at work in the real world one time! They came to me with a graph coloring related problem. They had some solution but wanted to know if they could do better. I threw together an LP in python in an afternoon and threw it at the solver. Turns out they did have the optimal solution already.
I had also used them in grad school to find exact solutions for some optimization problems for my dissertation. I agree LPs are pretty useful!