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's gravatar image

Sune
958413
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

Apart from Marcos suggestion, which I second, to answer your question directly:

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.

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.

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.

The second way is to store a flat list of open nodes storing differences to a reference point (e.g. the root node).

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.

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.

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.

link

answered 30 Sep '14, 13:07

Philipp%20Christophel's gravatar image

Philipp Chri...
1.0k27
accept rate: 22%

Although the other answers were quite enlightening as well, your answer addresses my question most directly.

(03 Oct '14, 09:25) Sune

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.

link

answered 30 Sep '14, 05:24

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
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

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.

link

answered 30 Sep '14, 07:28

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

edited 30 Sep '14, 10:01

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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×29
×14
×1

Asked: 30 Sep '14, 04:49

Seen: 2,742 times

Last updated: 03 Oct '14, 09:33

OR-Exchange! Your site for questions, answers, and announcements about operations research.