4 ms·

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

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.
    - hustwindmaple1 2y ago
      Reformulation is a good strategy for many hard problems. It might also be possible to add problem-specific cuts/heurstics to the solver so that it can solve it fast.
- djsavvy 2y ago
  Wow, this sounds interesting! Do you have a link to that thesis?
  - bjornsing 2y ago
    Unfortunately not. It’s on paper and in Swedish only.
nullc 2y ago
Are you aware of any survey papers on some of the strategies used by (near) state of the art solvers?
- sirwhinesalot 2y ago
  Not the same person but maybe "Mixed-Integer Nonlinear Programming: A Survey of Algorithms and Applications" could be a good start? I haven't read it yet. 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-programming-algorithms.html#mw_a9d9bbbe-5140-4798-85bc-493473c764eb https://nl.mathworks.com/help/optim/ug/mixed-integer-linear-...
- luiwammus 2y ago
  I am an academic in the field. A good starting point would be Tobias Achterberg's PhD thesis: "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
  - kragen 2y ago
    thank you very much! when i investigated the situation five years ago in https://dercuano.github.io/notes/linear-optimization-landscape.html#addtoc_2 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 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?
sirwhinesalot 2y ago
What's the situation with CPLEX these days? Is IBM still investing any serious resources into it? Gurobi keeps getting massively better (either in performance or expressiveness) every release.
- tomas789 2y ago
  As fare as I know it is jist a torso of its former glory. This is mostly the reason why we migrated to Gurobi.
- luiwammus 2y ago
  CPlex has shown no progression in the benchmarks in the past years, so it is safe to assume that the number of developers they have employed is either 0 or maybe 1.

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.
  - hustwindmaple1 2y ago
    Reformulation is a good strategy for many hard problems. It might also be possible to add problem-specific cuts/heurstics to the solver so that it can solve it fast.
djsavvy 2y ago
Wow, this sounds interesting! Do you have a link to that thesis?
- bjornsing 2y ago
  Unfortunately not. It’s on paper and in Swedish only.

nullc 2y ago

Are you aware of any survey papers on some of the strategies used by (near) state of the art solvers?

sirwhinesalot 2y ago
Not the same person but maybe "Mixed-Integer Nonlinear Programming: A Survey of Algorithms and Applications" could be a good start? I haven't read it yet. 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-programming-algorithms.html#mw_a9d9bbbe-5140-4798-85bc-493473c764eb https://nl.mathworks.com/help/optim/ug/mixed-integer-linear-...
luiwammus 2y ago
I am an academic in the field. A good starting point would be Tobias Achterberg's PhD thesis: "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
- kragen 2y ago
  thank you very much! when i investigated the situation five years ago in https://dercuano.github.io/notes/linear-optimization-landscape.html#addtoc_2 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 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?

sirwhinesalot 2y ago

What's the situation with CPLEX these days? Is IBM still investing any serious resources into it? Gurobi keeps getting massively better (either in performance or expressiveness) every release.

tomas789 2y ago
As fare as I know it is jist a torso of its former glory. This is mostly the reason why we migrated to Gurobi.
luiwammus 2y ago
CPlex has shown no progression in the benchmarks in the past years, so it is safe to assume that the number of developers they have employed is either 0 or maybe 1.