Branching rules in commercial MIP solvers

Question

I am working on a branch-and-cut algorithm, and I have spent quite some effort into improving the branching decisions that are made by commercial solvers, such as CPLEX and Gurobi. However, it was never successful: the standard branching by Cplex and Gurobi combined with the slight subtleties you can choose (focus lower bound, focus upper bound etc.) were always better than my own custom-made branching rules. My problem does not inherit any symmetry or whatsoever.

Now is that not very surprising, as the folks at CPLEX and Gurobi probably have spend years on researching efficient branching decisions. However, I am quite curious why my custom-made branching rules are never more effective (although they seem very smart!). To that end, I am curious what branching decisions are taken by these commercial solvers. Is there, somewhere, an overview of branching rules used by these solvers?

Edit: Main reason for asking this question is to find some justification to spend hours into designing problem-specific branching rules, or even beter, to quickly be able to decide to not spend time into designing problem-specific branching rules as they would probably not lead to a significant improvement of computational performance.

Answer 1

Tobias Achterberg's thesis includes a review of MIP solver technology from around 2009, including branching decisions and node selection.

Answer 2

Since branching rules are crucial for the performance of solvers they are also a very well guarded secret. I can say from experience that some form of reliability branching is sufficient to get a reasonable solver performance (not top of the class though). The devil is in the detail then because there are a ton of different ways of updating the pseudo-costs used in reliability branching (see reference to Tobias Achterbergs thesis and his paper Branching Rule Revisited). I am not aware of an overview paper that really describes all of this.

That said, a problem specific branching strategy should work better (if it is indeed clever) than the generic strategy implemented by the major solvers. Of course this only holds, if the solvers are not already doing great on a class of instances. In a a sense there is a certain minimum number of nodes that need to be processed for some problems, if a solver is already close to that, one can't expect huge improvements. On the other hand, if solvers are doing bad on a class of instances, chances are that a clever specialized strategy can yield huge benefits.

An example for that is Orbital Branching (Ostrowsky et al.) that identified a class of problems solvers did bad on and found a better strategy to deal with this specific class of problems. And it provided a fairly easy to implement way of doing this that did not disturb too many other parts of the solvers.