# Implementation of branch and bound algorithm

 2 1 Hi all, 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: I will have a node object or struct with the following members: node{ Array_of_fixed_variables; Lower_bound; level; } 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. I would be very happy to hear your comments on this! Thank you in advance. asked 30 Sep '14, 04:49 Sune 958●4●14 accept rate: 20% 2 The answer to your question, highly depends on for what task you need this implementation i.e commercial application, academic work or just "fun" for learning stuff. As other pointed out, I too would strongly advise only going for rolling your own B&B in the later case. Sketching the requirements for a B&B datastructure looks very simple, but you end up doing a lot more work than you expect. SCIP is probably a be better choice. (30 Sep '14, 16:01) Bo Jensen ♦ 1 For what it's worth, here's my implementation: I am using a TreeSet to store the node queue. (01 Oct '14, 02:24) Geoffrey De ... ♦ @Bo Jensen: It is for academic purposes. And maybe also a little bit for the fun of it. (03 Oct '14, 09:19) Sune

 4 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. 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. answered 30 Sep '14, 05:24 Marco Luebbecke ♦ 3.4k●1●6●15 accept rate: 16% Of course I should be an expert using SCIP as I attended the 2014 School on Column Generation. That is, however, not the case. Does SCIP support adding multiple child nodes? (03 Oct '14, 09:23) Sune
 2 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 here and here (the credit goes to Paul Rubin as usual). In addition to SCIP, I think ABACUS offers similar facilities that you could use. answered 30 Sep '14, 07:28 Ehsan ♦ 4.8k●3●11●22 accept rate: 16% Thanks for the links. It seems, however, that Schrödinger's cat ate the first link. (30 Sep '14, 09:19) Sune @Sune: Sorry. I fixed the link. (30 Sep '14, 10:03) Ehsan ♦ I think there is a problem with the cplex-work around: If I for example want to split a node $$Q$$ into three, say $$Q_i$$. Then I would like to only solve one LP in order to make this split, namely the one corresponding to $$Q$$. However, the proposed method would split $$Q$$ into $$Q_1$$ and $$Q_{\tilde{1}}$$. But $$Q_{\tilde{1}}$$ would not be split until after CPLEX has picked up the node, solved the corresponding LP and called the callback. So you end up solving too many LPs. When generating many nodes, this could be quite expensive. (30 Sep '14, 13:05) Sune I understand your point. Maybe Paul could comment on that issue. (30 Sep '14, 15:25) Ehsan ♦ 2 I'm not sure whether the extra node LPs are bad, good, or have minimal effect. Since the solver probably employs dual simplex on the child nodes, the number of extra pivots may be modest, and it's possible they actually save work (you may be doing pivots once that would otherwise be done at each child node). In any case, there is (currently) a trick to avoid them, at least in the Java API to CPLEX. Details are in a new blog post: http://orinanobworld.blogspot.com/2014/10/multiple-children-again.html. (02 Oct '14, 14:54) Paul Rubin ♦♦ Paul: I see your point. And thanks for taking your time to actually devise a trick. (03 Oct '14, 09:18) Sune showing 5 of 6 show 1 more comments
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: