Hi. I’ve written many mixed-integer programming problems and sent them to solvers (HiGHS and Gurobi). The solvers seem to follow this pattern.
Adding cuts at the root node (Gomory cut among other cuts)
Doing a branch and bound search.
However, it looks like most effort was spent on (1). Not so much effort was spent on (2), or at least as I know. Why is this the case?
For the sake of comparison, here is the chess engine Stockfish. It has so many search heuristics. Some would not apply to MIP, but it shows how many heuristics can improve the algorithm from a simple search algorithm. https://www.chessprogramming.org/Stockfish
Back to MIP… the focus seems skewed on finding cuts. Why is this?
Am I unaware of the effort put into the search?
Is adding search heuristics to MIP much more difficult than adding a chess engine?
The big difference is that search is problem specific and MILP solvers don’t know nearly as much about the domain. Minimax search is a fun case where the problem is recursive so at every level, the solution to the problem is trivial if you’ve solved the problem 1 layer down. This means that in Chess, you only need 1 search strategy and it will massively improve everything. In MILP, by contrast there isn’t a clean structure, so any search needs to find connected subsets with a given structure and any improvement will only be useful for a very small number of places.
I don’t think that is entirely accurate. Industrial MILP solvers also have a great variety of search (so-called diving) heuristics to generate feasible solutions quickly, which helps prune more branches of the Branch&Bound tree. I think @mbesancon would be the best person to ask.
This simple question sadly does not have a short answer
The shortest explanation I can give is that current experience suggests that generating cuts at the root is a more efficient strategy than focusing on branching.
[longer story]
Background: MIP solvers like Gurobi, HiGHS, SCIP, etc… are handed a MIP instance, and must do two things: 1) find a feasible solution with objective as good as possible (the primal side) and 2) prove that this solution is optimal (the dual side), i.e., that there does not exist a feasible solution with better objective value.
Empirically, in most cases, it is “easier” (i.e. faster) to find very good primal solutions than to prove their optimality. Finding good solutions is the role of heuristics. Proving optimality is done by cuts and branching. (naturally, cuts and branching can improve heuristics, but I’m keeping things simple).
So why do solvers typically generate cuts somewhat aggressively at the root node (i.e. before branching)? Because our experience suggests that it is relatively hopeless to solve (large) instances purely by branching. My general expectation with MIP solving is that if I see a lot of branching being done, then the solver likely won’t terminate before the universe ends.
There is limited theoretical understanding of the relationship between cuts and branching in MIP solving. The few works I am aware of are (note that both papers were published in 2023…):
Finding good, general branching strategies that cater to general MIP instances is a very open avenue of research, and a tough yet-to-be-cracked-if-ever nut.
