Faster Integer Programming
cacm.acm.org
cacm.acm.org
Although the number of variables or constraints is not a good measure of the hardness of an ILP, "tens of thousands" is not that unusual. During my PhD, I often solved programs with millions of variables and constraints. These programs were so large that even "building" them in the solver library took several seconds. Impressively, gurobi was often able to optimize them in under 24 hours. I have two results here where gurobi solved 1M * 8M problems to optimality in under 2 hours. That was several years ago, so I expect newer versions to be even faster. Even for larger problems (around 5M * 50M) it often found provably near-optimal solutions (within 5% of optimality) very fast. gurobi is really an impressive piece of software, and free for academic use.
Completely agree that size is not a good proxy for estimating MIP difficulties. Internally we colllected a bunch of very hard problems to sovle from different domains. Some are actually pretty small, say a few thousand variables/constraints. IMHO what made hard problems difficult to solve is actually the 'intneral structure' of the problems. And modern industry solvers all have a lot of built-in heurstics to take advantages of the structures, i.e., what kind of cuts, presolve/diving/branching strategy to apply, how to get the bounds ASAP.
Interestinglly at some point some folks even tried using machine learning to predict strategies. Didn't work quite well back then (10+ years ago). There was some work of using seq2seq for MIP (pointer network, I think) a few years ago; worked OK. So I'm really looking forward to some breakthroughs by LLM.
It's a shame that after IBM aquired ILOG (which owns CPLEX), most of the ppl left for Gurobi.
20 years ago I wrote a master’s thesis in computer vision. The stereo matching algorithm I developed could be expressed as a big integer linear program. But after pondering it for some time I realized it could also be expressed as a dynamic programming problem, with tiny integer linear programs as subproblems. Reduced the runtime by like a factor of 1000x, or more.
I feel most of those big search problems could be solved much easier and quicker with some form of annealing/tree search/dynamic or greedy algorithms with results very close to the theoretical linear optimum
But of course those won't get you a thesis ;)
In this case I could prove it was the globally optimal solution.
But this was only possible of course due to the internal structure of the problem: it was in effect a simpler problem hiding within a linear integer program. Standard solvers couldn’t find this structure, but it was possible to do by hand.
It might also be possible to add problem-specific cuts/heurstics to the solver so that it can solve it fast.
HiGHS is the best open source MILP solver at the moment, and MATLAB of all things has a pretty good explanation of how it works internally: https://nl.mathworks.com/help/optim/ug/mixed-integer-linear-...
"Constraint Integer Programming"
It details the implementation of SCIP, which is one of the leading open source solvers, and explains some of the most important tricks.
That said, there is a lot of literature out there; if you're interested in a particular aspect like e.g. presolving or cutting planes, then feel free to ask me further questions. It is worth noting that the implementation specifics are hidden by the top commercial solvers, so these are difficult to find anywhere
when i investigated the situation five years ago in https://dercuano.github.io/notes/linear-optimization-landsca..., scip was not open source, though zimpl was. looking at https://github.com/scipopt/scip?tab=License-1-ov-file#readme, it appears that scip has become open-source since then, which is very welcome news!
how does highs compare to scip?
We need more optimization in this industry.
The Windows 11 context menu lag (and overall Windows bloat) is a product of Conway's law. Microsoft creates bloated software because it's a monopoly. So, "optimization" in this case would essentially be antitrust action.
I think the explanation isn't quite as simple as you make it seem.
It's also that you're expected to update windows whether or not they've actually improved performance. Why would microsoft prioritize that when the bulk of their sales are driven by other concerns, like enterprise sales and what some might call basic functionality (e.g. Windows Defender, when it was first released).
Hell, now they're moving to a service model and there's even less reason to court consumers directly.
How about matrices used by RAF/AAF targeters for mincut purposes, eg https://en.wikipedia.org/wiki/Oil_campaign_of_World_War_II ?
* surprisingly, en.wikipedia has more information than ru.wikipedia, but neither even has a hint as to headcounts over the years, let alone more technical details.
Obviously it didn’t work out though.
The other book worth getting is “red plenty”.
It is available on annas archive. Along with other similar books (Search: "Planning in the USSR").
LOOK UPON ME AND DESPAIR!
What kind of hardware did you need for such large problems? Single machine or cluster?
E.g., do you assume that the optimal value is the one produced by the non-integer LP?
Great thing is that you can find the dual really easily and each feasible solution of the primal problem can be used to get a feasible solution of the dual.
The math behind that is really neat.
For several problems you can prove lower and/or upper bounds for the optimal results. For example you can prove that a route between two points may not be shorter than their distance.
If you use LP in production you often don't care about optimality and can work with suboptimal results very well. Worst case you stop after a timeout and just pick the best result.
Edit: I forgot to mention that during solving of a LP you usually get dynamically computed bounds. The branch and bounds algorithm works by computing bounds on relaxed problems that give upper bounds for the original problem.
We should be happy that many of the best tools in other areas are free.
Questions:
1) Was the problem able to be solved with one machine?
2) Was the problem reliably able to be solved within a time-bound, or was it "spiky"?
3) Was the solution all or nothing? Aka would you get a partial/suboptimal solution after a time-bound?
1) It is usually done on a single machine. Often times even on single core.
2) Spikiness of the solve time is a real problem in practice.
3) You get partial solutions but they tend to be fare apart but with great improvements.
my notes on the landscape five years ago: https://dercuano.github.io/notes/linear-optimization-landsca...
it's in the public domain, so you can take the article and make your own copy of it with the expanded octave section you wish for
That works really well in practice (because most solvers relax your (mixed) integer programming problem to a fully continuous problem anyway, and then try to 'repair' any fractional solutions as necessary), but is apparently really hard to analyse in theory.
I'm not sure I understand this. It's usually the opposite way
A linear problem is super fast. With integers it goes to branch and bound (a kinda fancy name for manual search). But lots of 1/0 variables just make your problem slow
If the parameters need to be integers, then it becomes way more difficult. The optimum for the continuous case is probably not valid. So you need to enumerate a lot of points.
If the parameters can just be 0 or 1, it's a special case of the integer case: you still need to enumerate, but way less points.
Hope this helps
Sounds like the simplex method, which is complicated and/or has potentially quite bad worst-case complexity. (You can implement it naively in very little code, and I’ve done this on some programming competitions, but you shouldn’t do this for serious use.) You can achieve better asymptomatic behavior with “interior point” methods, where you arrange for all the constraints to repel your optimum, solve a (nice, convex, polynomial time) problem to find the best point that touches none of the constraints, and then relax the repulsion from the constraints a bit and iterate. All that being said, a good simplex implementation may well run circles around interior point methods for well-behaved inputs.
(I’m a fan of interior point methods because they can also naturally handle fairly large classes of nonlinear constraints while still running in more or less polynomial time. Check out CVXOPT for a nice example of what you can do with great ergonomics.)