Branch and Bound (B&B) is a general solution approach to solve combinatorial optimisation problems. I was wondering how B&B is implemented in practice. Although it may be relevant, but I am not looking for an explanation of why/how B&B works. Instead, I am interested in learning how this is normally implemented in a programming language (Python, Java, C++ etc), what data structures are better to use and why. Any information regarding the standard practice is appreciated.
2
-
3$\begingroup$ Since many of the implementations are open source, perhaps you could look at some of the actual code, in whatever programming language you know best. $\endgroup$– John ColemanCommented Jan 7, 2020 at 15:46
-
$\begingroup$ @JohnColeman Unfortunately implementation details for most of OR algorithms used in academic articles is not published. The existing opensource implementation often consists of a huge library and it may be too general and difficult for learning B&B details only. Having said that, after learning some standard practice regarding B&B implementation it would be extremely helpful (and easier) to look at these source codes. $\endgroup$– rasulCommented Jan 8, 2020 at 23:24
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
7
Read the ph.d. thesis of Tobias Achterberg where he describes the solver Scip.
Have fun.
-
4$\begingroup$ this answer was downvoted (I upvoted it to zero :)); a one liner may sound rude as an answer, however, this IS the answer, in my view also. And fun it is. $\endgroup$ Commented Jan 7, 2020 at 8:17
-
7$\begingroup$ Sorry, but answer was not meant to be rude in way. I think building optimizers is fun so the have fun is meant in a sincere way. Note Tobias got the Beale-Orchard-Hays Prize for his thesis. I was on the committee. $\endgroup$ Commented Jan 7, 2020 at 8:25
-
2
-
2$\begingroup$ I understand your point but in this case I really think my answer is really the best answer and not just a comment. So what I did was very conscious. $\endgroup$ Commented Jan 7, 2020 at 11:36
-
3$\begingroup$ I consider this a full answer. I also agree with Shakespeare that "brevity is the soul of wit". $\endgroup$– prubin ♦Commented Jan 7, 2020 at 16:31
$\begingroup$
$\endgroup$
Check COIN-OR ALPS code (in C++) and Yan Xu's dissertation for explanation. He explains a scalable parallel branch and bound algorithm and presents experiments solving Knapsack instances with up to 2048 cores. You can ignore the parallelization related parts in code and the text if not interested.
$\begingroup$
$\endgroup$
What makes any branch-and-bound implementation tick is the heuristics that accompany the algorithm, not branch-and-bound itself. I start by explaining branch-and-bound to frame why we need the heuristics, but if you are interested in implementation, you can skip to the end.
Why branch-and-bound works
For simplicity I will assume bisection branch and bound on a single variable, i.e., each branching action creates two new nodes the union of which is equivalent to the parent domain.
Now let's also assume that all our variables are binary. If the problem has a feasible solution, there is at least one binary combination which yields the best objective value. To prove global optimality, we need to not only locate this combination, but also to prove that no better solution exists anywhere else.
If we start fixing variables successively through branching, the result is a binary tree where each leaf node represents a unique variable combination. For a full binary problem that's $2^n$ combinations (btw for continuous branch-and-bound that's actually infinity), which is also the worst-case complexity in this case.
Branch-and-bound is a heuristic method that allows us to prove global optimality (or to simply find a feasible solution) without necessarily having to create and explore all $2^n$ nodes. This is possible if we have two things: the ability to derive rigorous bounds on the value of the objective function after each branching action, and a feasible solution to the actual problem. Using those two pieces of information we can eliminate a massive number of nodes from the search because, through the bounds, we can prove that certain binary combinations cannot possibly give us a better objective than the feasible solution we already have. Crucially, this also means that we need good enough primal heuristics to find feasible solutions for branch-and-bound to work.
Overall, this is amazing, because with good primal and acceleration heuristics, it is possible to achieve polynomial (or even almost linear in some cases) average runtime complexity. This beats the alternative, which is to always explore exponentially many nodes. The counterpoint is that, without good heuristics, branch-and-bound can take centuries to converge instead of seconds.
Implementation
W.r.t. data structures, it doesn't really matter to be honest, because the cost of managing the tree is insignificant compared to the cost of everything else in a branch-and-bound algorithm, especially in C++. You will only see the cost of sorting or inserting nodes if you are solving 1-2 variable problems, and even then it will be very small.
What is interesting instead is the spatial complexity of tree management. If we have, say, 1m variables, the naive way is to copy the bounds of all variables to represent each new node created. That's a lot of memory. Instead many implementations (e.g., MINOTAUR), represent each node as a modification compared to its parent (kinda like Git). This means that instead of storing 2m new values, we only need to store 2. The drawback of course is slower lookup speed to retrieve all bounds for each node, but as I mentioned earlier that's not really significant in the grand scheme of things.
Professional tip: we typically use more than one data structure to store information in a high performance solver, and switch between structures on the fly when a structure starts scaling badly (similar to the small string optimisation in C++).
Heuristics-wise there are literally thousands. The most important by far are domain reduction methods, followed by branching variable selection heuristics. Beyond those, we also need a local solver/primal heuristic capable of actually finding the global solution without us having to actually fix all variables. This last bit is by far the most challenging for difficult problems.
$\begingroup$
$\endgroup$
This Github repository has the Java implementation of the Branch and Bound for solving VRP.
