4 ms·

Faster Integer Programming

167 points by pseudolus 2y ago

basementcat 2y ago
Note this is an improvement to a theoretical bound and doesn’t present any immediate improvements for most practically solvable Integer Programming problems (which are generally solved with more efficient heuristics).
- eru 2y ago
  Yes, and in practice you also often want to solve 'mixed' integer programming problems. Ie those that have both continuous and integer variables. 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.
- tomas789 2y ago
  Once we know it can be done, there is much higher chance somebody will look really hard into it and with a bit of luct, they will come up with a practical algorithm. Or at least good one for some edge cases.
kragen 2y ago
this is a pretty good overview; it's unfortunate that they omitted linear from the title of the article, because it's pretty crucial my notes on the landscape five years ago: https://dercuano.github.io/notes/linear-optimization-landscape.html https://dercuano.github.io/notes/linear-optimization-landsca...
- johnisgood 2y ago
  I wish the original article offered code, similarly to yours. I wish you could elaborate more in the Octave section though.
  - kragen 2y ago
    dercuano is a book i published in 02019; it's not being updated. you can download the final copy at http://canonical.org/~kragen/dercuano-20191230.tar.gz http://canonical.org/~kragen/dercuano-20191230.tar.gz or a somewhat inferior pdf version for cellphones at http://canonical.org/~kragen/dercuano.20191230.pdf http://canonical.org/~kragen/dercuano.20191230.pdf 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
- unnah 2y ago
  The optimization solver landscape changes slow enough that a 5 year old overview it is still very relevant. However, in recent years the open source solver HiGHS (https://highs.dev/ https://highs.dev/) has emerged and even surpassed the older open source solvers.
  - kragen 2y ago
    thank you very much!
- sevensor 2y ago
  Linearity has been a sticking point since the very beginning, with the famous exchange between Hotelling and Von Neumann. MILP solvers are amazing, and what they can solve feels like it should be impossible, but even so you get stuck sometimes banging nonlinear pegs into linear holes.
deleted 2y ago
[deleted]
wiz21c 2y ago
It misses Julia's JuMP: https://jump.dev/JuMP.jl/stable/ https://jump.dev/JuMP.jl/stable/
- SkiFire13 2y ago
  That seems to be only a frontend for declaring the problems, it is not a solver itself.
  - wiz21c 2y ago
    ah yes, my memory did not serve me well :-( thanks for your comment :-)
lqet 2y ago
> “In practice they are very efficient. They solve industrial-scale problems all the time,” sometimes with tens of thousands of variables. 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.
- geysersam 2y ago
  Interesting, do you mind telling a bit about the context where the problems you were solving arose? What was the application? What kind of hardware did you need for such large problems? Single machine or cluster?
  - lqet 2y ago
    It was a graph drawing problem, solved on a single 16 core machine with around 64 GB of RAM.
- KeplerBoy 2y ago
  I love how researchers state that a piece of code doing actual work is "slow", once it takes a few seconds to run and yet windows 11 often takes multiple seconds to show me the context menu, when i right click something. We need more optimization in this industry.
  - tazu 2y ago
    > 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.
brandonpelfrey 2y ago
I helped implement production and labor planning software on top of FICO xpress some years ago. The paradigm of LP/ILP was all new to me though I was very much into math. Our software was solving hierarchical/nested optimization problems involving millions of variables and constraints every 15 minutes. It felt like magic that this was possible. I would really encourage anyone that has never worked with these tools before to explore them as it can open a palette of tools and ideas you may not have thought of before. A great free way to get into this is to read the examples and use PuLP for Python.
- pradn 2y ago
  Pretty cool you got to see this stuff in the real world! 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?
  - tomas789 2y ago
    Not an author but 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.
    - pradn 2y ago
      Thank you, that's useful!
- petters 2y ago
  The best solvers are really impressive. Unfortunately, they also cost a very large sum of money. We should be happy that many of the best tools in other areas are free.
raverbashing 2y ago
> “The proof basically says that you can solve an integer linear program, in theory, almost as well as you can solve one where the integer variable is only zero or one,” 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
- michaelmior 2y ago
  I believe they're talking about unbounded integer programming vs binary integer programming.
- toolslive 2y ago
  If the parameters are allowed to be real numbers, it's very fast. just move "up" to an edge (constraint), then follow the edges upward to your maximum. 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
  - amluto 2y ago
    > If the parameters are allowed to be real numbers, it's very fast. just move "up" to an edge (constraint), then follow the edges upward to your maximum. 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.)
Hugsun 2y ago
What struck me when writing integer programs was how quickly the rule and variable count grows with the problem. Expressing simple ideas often required O(n²) rules as every pair of objects needed constrained relations. The default solver in PuLP solved all the problems with ease.

167 points by pseudolus 2y ago

Note this is an improvement to a theoretical bound and doesn’t present any immediate improvements for most practically solvable Integer Programming problems (which are generally solved with more efficient heuristics).

eru 2y ago
Yes, and in practice you also often want to solve 'mixed' integer programming problems. Ie those that have both continuous and integer variables. 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.
tomas789 2y ago
Once we know it can be done, there is much higher chance somebody will look really hard into it and with a bit of luct, they will come up with a practical algorithm. Or at least good one for some edge cases.

kragen 2y ago

this is a pretty good overview; it's unfortunate that they omitted linear from the title of the article, because it's pretty crucial my notes on the landscape five years ago: https://dercuano.github.io/notes/linear-optimization-landscape.html https://dercuano.github.io/notes/linear-optimization-landsca...

johnisgood 2y ago
I wish the original article offered code, similarly to yours. I wish you could elaborate more in the Octave section though.
- kragen 2y ago
  dercuano is a book i published in 02019; it's not being updated. you can download the final copy at http://canonical.org/~kragen/dercuano-20191230.tar.gz http://canonical.org/~kragen/dercuano-20191230.tar.gz or a somewhat inferior pdf version for cellphones at http://canonical.org/~kragen/dercuano.20191230.pdf http://canonical.org/~kragen/dercuano.20191230.pdf 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
unnah 2y ago
The optimization solver landscape changes slow enough that a 5 year old overview it is still very relevant. However, in recent years the open source solver HiGHS (https://highs.dev/ https://highs.dev/) has emerged and even surpassed the older open source solvers.
- kragen 2y ago
  thank you very much!
sevensor 2y ago
Linearity has been a sticking point since the very beginning, with the famous exchange between Hotelling and Von Neumann. MILP solvers are amazing, and what they can solve feels like it should be impossible, but even so you get stuck sometimes banging nonlinear pegs into linear holes.

deleted 2y ago

[deleted]

wiz21c 2y ago

It misses Julia's JuMP: https://jump.dev/JuMP.jl/stable/ https://jump.dev/JuMP.jl/stable/

SkiFire13 2y ago
That seems to be only a frontend for declaring the problems, it is not a solver itself.
- wiz21c 2y ago
  ah yes, my memory did not serve me well :-( thanks for your comment :-)

lqet 2y ago

> “In practice they are very efficient. They solve industrial-scale problems all the time,” sometimes with tens of thousands of variables. 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.

geysersam 2y ago
Interesting, do you mind telling a bit about the context where the problems you were solving arose? What was the application? What kind of hardware did you need for such large problems? Single machine or cluster?
- lqet 2y ago
  It was a graph drawing problem, solved on a single 16 core machine with around 64 GB of RAM.
KeplerBoy 2y ago
I love how researchers state that a piece of code doing actual work is "slow", once it takes a few seconds to run and yet windows 11 often takes multiple seconds to show me the context menu, when i right click something. We need more optimization in this industry.
- tazu 2y ago
  > 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.

brandonpelfrey 2y ago

I helped implement production and labor planning software on top of FICO xpress some years ago. The paradigm of LP/ILP was all new to me though I was very much into math. Our software was solving hierarchical/nested optimization problems involving millions of variables and constraints every 15 minutes. It felt like magic that this was possible. I would really encourage anyone that has never worked with these tools before to explore them as it can open a palette of tools and ideas you may not have thought of before. A great free way to get into this is to read the examples and use PuLP for Python.

pradn 2y ago
Pretty cool you got to see this stuff in the real world! 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?
- tomas789 2y ago
  Not an author but 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.
  - pradn 2y ago
    Thank you, that's useful!
petters 2y ago
The best solvers are really impressive. Unfortunately, they also cost a very large sum of money. We should be happy that many of the best tools in other areas are free.

raverbashing 2y ago

> “The proof basically says that you can solve an integer linear program, in theory, almost as well as you can solve one where the integer variable is only zero or one,” 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

michaelmior 2y ago
I believe they're talking about unbounded integer programming vs binary integer programming.
toolslive 2y ago
If the parameters are allowed to be real numbers, it's very fast. just move "up" to an edge (constraint), then follow the edges upward to your maximum. 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
- amluto 2y ago
  > If the parameters are allowed to be real numbers, it's very fast. just move "up" to an edge (constraint), then follow the edges upward to your maximum. 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.)

Hugsun 2y ago

What struck me when writing integer programs was how quickly the rule and variable count grows with the problem. Expressing simple ideas often required O(n²) rules as every pair of objects needed constrained relations. The default solver in PuLP solved all the problems with ease.