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
For each "or" node in the result, the result also contains one of its descendants.
For each "and" node in the result, the result contains all its descendants.
The result contains a set of "root" nodes (given as part of the input).
The total cost (sum over the non-negative costs) is minimized.
The induced subgraph from the result is acyclic. (we can ignore it for now)
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)
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.
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
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:
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.