Custom heuristics for MIP

[pca006132]

Is there a way to influence node selection during branch-and-bound, as well as add heuristics to obtain good MIP feasible solutions? For our problem (explained below), we have some natural variable order that may allow the solver to prune the search space efficiently, and we have simple algorithms to generate good MIP feasible solutions that may help to get a tighter upper bound during B&B.

The only non-trivial solver example I saw in the example directory is the branch-and-price example, but it seems to be doing a custom branch-and-price loop, and not using the cut generators implemented in the MIP algorithm (if I understand it correctly). And apparently there is no way to invoke the cut generators from public APIs.

---

Context: (Not sure if the following should be moved to discussion or a new issue)

I'm currently working on e-graph extraction problem. We have a directed graph with two kinds of nodes, "or" (also called e-class) and "and" (e-node) nodes, as well as non-negative costs associated to each node. We want to extract a set of nodes such that

1. For each "or" node in the result, the result also contains one of its descendants.
2. For each "and" node in the result, the result contains all its descendants.
3. The result contains a set of "root" nodes (given as part of the input).
4. The total cost (sum over the non-negative costs) is minimized.
5. The induced subgraph from the result is acyclic. (we can ignore it for now)

There are some heuristics as well as ILP encoding in https://github.com/egraphs-good/extraction-gym using cbc.
ILP encoding works, but it is slow for larger instances (>= 10k variables). When reading the CBC documentation (https://coin-or.github.io/Cbc/cbcmodelclass#impacting-the-solution-process), it seems that it is a common practice to provide custom heuristics when the problem is hard. (I'm not familiar with OR, so I am not sure if this is really a common practice)

The heuristics I want to implement for now:

1. Provide custom branching heuristic. We want to prefer topological order in the e-graph, as this may enable graph pruning. (the graph can be cyclic, but the cycles are typically small, so it should be fine)
2. Perform e-graph pruning after each step during B&B. This will set a lot of nodes to 0 and can probably reduce the search space. For example, we can remove nodes that subsume the others, or collapse part of the graph.

I'm just wondering if this can be implemented with public APIs in HiGHS, or if I will to modify the source to add custom heuristics.

[jajhall]

Thanks for setting out your questions and background in such detail, but the short answer is "no" to them all. The HiGHS MIP solver was written to give general performance as a "black box", and only slowly are we adding any user control. I note that what you ask for in HiGHS appears not to be available in Gurobi, and even with their VarBranch and BranchDirparameters the documentation observes that "Changing the value of this parameter rarely produces a significant benefit". The tree search in sophisticated MIP solvers like HiGHS is far from being a simple "branch-and-bound" procedure, so modifying the default behaviour is (a) challenging to implement and (b) likely to give disappointing results. It may be possible in CBC, but this is a significantly simpler (and inferior) solver. I strongly encourage you not to modify the source to add custom heuristics.

[pca006132]

I see, thanks for the prompt reply!