Answers to: Implementation of branch and bound algorithmhttp://www.or-exchange.com/questions/10288/implementation-of-branch-and-bound-algorithm<p>Hi all,</p>
<p>I am at the moment implementing a branch and bound algorithm for a bi-objective combinatorial optimization problem. Up until now, every time I needed a branch and bound/cut framework, I have used CPLEX and its callbacks. However, this time, every time I split a node after solving the LP-relaxation I need to create more than two nodes (sometimes many nodes \(>3\) ). For that reason I will implement my own framework. My background in computer science is however rather limited so I would like to hear how you usually implement that stuff. My idea is to implement a depth first search in the following way:</p>
<p>I will have a node object or struct with the following members:</p>
<pre><code>node{
Array_of_fixed_variables;
Lower_bound;
level;
}
</code></pre>
<p>My idea was then to simply store the nodes in a vector by appending nodes in the end as they are created and pop them from the end when a new nodes is chosen. This way, I should quite easily have access to a valid lower bound: the lower bound of the node at index zero of the vector storing the nodes. Storing the level of the node should not be necessary for the depth first. However, replacing the vector with a priority queue could be used if one wants to switch to breadth first search.</p>
<p>I would be very happy to hear your comments on this! Thank you in advance.</p>enTue, 30 Sep 2014 13:07:48 -0400Answer by Philipp Christophelhttp://www.or-exchange.com/questions/10288/implementation-of-branch-and-bound-algorithm/10297<p>Apart from Marcos suggestion, which I second, to answer your question directly:</p>
<p>For a depth first search your idea to use a stack is pretty much the way to go. But note that for that you don't really need a node object or a node stack. The most lightweight implementation you can do only keeps a stack of bounds changed.</p>
<p>For a more general branch and bound I'll simplify it a bit so you get the idea. There are broadly speaking two ways to do it. </p>
<p>The first way is to store nodes in a tree structure and a new node only stores the changes to its parent. The advantage is that you actually know the structure of the tree and can traverse it back to the root. You might save memory, but you might also need more memory since you are not free to delete nodes as long as they have any children. I think SCIP works like this more or less, but I am no SCIP expert.</p>
<p>The second way is to store a flat list of open nodes storing differences to a reference point (e.g. the root node).</p>
<p>For both approaches, if you want to manage large trees, you eventually have to consider partitioning the open nodes into interesting ones and not-so intersting ones so that your selection algorithm works fast enough.</p>
<p>Another thing to consider is that MIP solvers also store warmstart information on the nodes (e.g. a basis of the parent node). If you do depth first, there is no need to do that since you can warm- (and even hot-)start naturally if the API of your solver handles it well.</p>
<p>For a proof of concept it might well be enough to implement a simple depth first approach and that might be simpler than learning to work in a solver framework. If that works, you know it might be worth refining the implementation. If that does not work, you really don't know if a better tree management would fix it.</p>Philipp ChristophelTue, 30 Sep 2014 13:07:48 -0400http://www.or-exchange.com/questions/10288/implementation-of-branch-and-bound-algorithm/10297Answer by Ehsanhttp://www.or-exchange.com/questions/10288/implementation-of-branch-and-bound-algorithm/10291<p>There is a workaround in CPLEX to do what you need. Essentially, you need to create copies of the original node, while creating the child nodes and carefully branch on each one to mimic branching on more than two nodes. For more information, you might see <a href="http://orinanobworld.blogspot.com/2010/06/when-octomom-solves-milps.html">here</a> and <a href="http://orinanobworld.blogspot.com/2012/06/birthing-litter-in-cplex.html">here</a> (the credit goes to Paul Rubin as usual).</p>
<p>In addition to SCIP, I think <a href="https://projects.coin-or.org/ABACUS">ABACUS</a> offers similar facilities that you could use.</p>EhsanTue, 30 Sep 2014 07:28:45 -0400http://www.or-exchange.com/questions/10288/implementation-of-branch-and-bound-algorithm/10291Answer by Marco Luebbeckehttp://www.or-exchange.com/questions/10288/implementation-of-branch-and-bound-algorithm/10289<p>Sune, I don't know if performance is an issue in your case. Usually, man/women power is an issue, so I would really, really suggest you to go with a framework that already support most of what you need, all the B&B administration of nodes etc. You only need your customized branching rule (create more than two childs), that's it. Me personally, I would choose SCIP, but this is a matter of taste.</p>
<p>Costs you more in learning SCIP, if you don't already know it, but saves you lot of debugging all the administrative and performance issues in B&B.</p>Marco LuebbeckeTue, 30 Sep 2014 05:24:57 -0400http://www.or-exchange.com/questions/10288/implementation-of-branch-and-bound-algorithm/10289