6 ms·

> “In practice they are very efficient. They solve industrial-scale problems all the time,” sometimes with tens of thousands of variables. Although the number

by 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.
  - michaelmior 2y ago
    I think the other piece going into it is that hardware keeps getting faster. I would imagine especially so the hardware of the average Windows developer. If something doesn't generally appear to be slow to those building it, they're unlikely to spend a lot of time optimizing.
    - tazu 2y ago
      I'm a fan of including benchmarks in CI pipelines. The Windows developers should have a historical record [1] of the performance degradation and be forced to look at it daily. [1]: https://x.com/jmmv/status/1671670996921896960 https://x.com/jmmv/status/1671670996921896960
      - juliangoldsmith 2y ago
        To be fair, that machine is pretty high-spec for NT 3.51, given that the minimum requirements are 12 MB RAM and a 386 (which tops out at 40 MHz). It'd certainly be nice to see that kind of performance in newer Windows versions, though.
    - darby_nine 2y ago
      > I think the other piece going into it is that hardware keeps getting faster. 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.
  - lawn 2y ago
    Every other website is a mess of bloated and slow JavaScript code, both large and small sites alike. I think the explanation isn't quite as simple as you make it seem.
- kragen 2y ago
  it depends on what you're using it for. if you use an optimization algorithm after every keystroke to relayout the paragraph you're typing, it had better not take a few seconds to run. (and indeed there are optimization algorithms for that problem in particular that are much faster than a few seconds.)
082349872349872 2y ago
Anyone have any idea how large Gosplan's* matrices were? How about matrices used by RAF/AAF targeters for mincut purposes, eg https://en.wikipedia.org/wiki/Oil_campaign_of_World_War_II 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.
- spitfire 2y ago
  I have the book “planning in the user” somewhere packed away. I remember it speaking about the number of variables and size of the problem in it. Sorry I don’t remember the numbers off the top of my head. Obviously it didn’t work out though. The other book worth getting is “red plenty”.
  - spitfire 2y ago
    Planning in the U.S.S.R Problems of theory and Organisation It is available on annas archive. Along with other similar books (Search: "Planning in the USSR"). LOOK UPON ME AND DESPAIR!
hustwindmaple1 2y ago
I was on CPLEX team for a few years. Core developers are all PhDs from Stanford/MIT and etc. So it's very hardcore stuff, no less than AI research. 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.
- bjornsing 2y ago
  > IMHO what made hard problems difficult to solve is actually the 'intneral structure' of the problems. 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.
  - raverbashing 2y ago
    Not that uncommon. 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 ;)
    - bjornsing 2y ago
      > with results very close to the theoretical linear optimum 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.
CoastalCoder 2y ago
Out of curiosity, how does one prove near optimality in problems like this? E.g., do you assume that the optimal value is the one produced by the non-integer LP?
- thargor90 2y ago
  LPs can prove optimality of a result but sometimes this is to expensive and you stop as soon as you reach near optimality based on known bounds. 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.
- tomas789 2y ago
  It is called duality. For each linear program that is maximizing, you can find a dual linear program wich is minimization. They both have the same optimal objective value. Thus one serves as a lower bound and the other as an upper bound on the optimal objective value. The gap between them is used to measure the closeness to the global optima. 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.

by lqet 2y ago

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.
- michaelmior 2y ago
  I think the other piece going into it is that hardware keeps getting faster. I would imagine especially so the hardware of the average Windows developer. If something doesn't generally appear to be slow to those building it, they're unlikely to spend a lot of time optimizing.
  - tazu 2y ago
    I'm a fan of including benchmarks in CI pipelines. The Windows developers should have a historical record [1] of the performance degradation and be forced to look at it daily. [1]: https://x.com/jmmv/status/1671670996921896960 https://x.com/jmmv/status/1671670996921896960
    - juliangoldsmith 2y ago
      To be fair, that machine is pretty high-spec for NT 3.51, given that the minimum requirements are 12 MB RAM and a 386 (which tops out at 40 MHz). It'd certainly be nice to see that kind of performance in newer Windows versions, though.
  - darby_nine 2y ago
    > I think the other piece going into it is that hardware keeps getting faster. 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.
- lawn 2y ago
  Every other website is a mess of bloated and slow JavaScript code, both large and small sites alike. I think the explanation isn't quite as simple as you make it seem.
kragen 2y ago
it depends on what you're using it for. if you use an optimization algorithm after every keystroke to relayout the paragraph you're typing, it had better not take a few seconds to run. (and indeed there are optimization algorithms for that problem in particular that are much faster than a few seconds.)

082349872349872 2y ago

Anyone have any idea how large Gosplan's* matrices were? How about matrices used by RAF/AAF targeters for mincut purposes, eg https://en.wikipedia.org/wiki/Oil_campaign_of_World_War_II 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.

spitfire 2y ago
I have the book “planning in the user” somewhere packed away. I remember it speaking about the number of variables and size of the problem in it. Sorry I don’t remember the numbers off the top of my head. Obviously it didn’t work out though. The other book worth getting is “red plenty”.
- spitfire 2y ago
  Planning in the U.S.S.R Problems of theory and Organisation It is available on annas archive. Along with other similar books (Search: "Planning in the USSR"). LOOK UPON ME AND DESPAIR!

hustwindmaple1 2y ago

I was on CPLEX team for a few years. Core developers are all PhDs from Stanford/MIT and etc. So it's very hardcore stuff, no less than AI research. 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.

bjornsing 2y ago
> IMHO what made hard problems difficult to solve is actually the 'intneral structure' of the problems. 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.
- raverbashing 2y ago
  Not that uncommon. 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 ;)
  - bjornsing 2y ago
    > with results very close to the theoretical linear optimum 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.

CoastalCoder 2y ago

Out of curiosity, how does one prove near optimality in problems like this? E.g., do you assume that the optimal value is the one produced by the non-integer LP?

thargor90 2y ago
LPs can prove optimality of a result but sometimes this is to expensive and you stop as soon as you reach near optimality based on known bounds. 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.
tomas789 2y ago
It is called duality. For each linear program that is maximizing, you can find a dual linear program wich is minimization. They both have the same optimal objective value. Thus one serves as a lower bound and the other as an upper bound on the optimal objective value. The gap between them is used to measure the closeness to the global optima. 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.