I have a non-linear objective function F of p binary arguments…
I would like to solve this using a branch and bound method, using a continuous relaxation to acquire the bound.
The continuous relaxation of F, however, is not convex. Instead I have another function which lower bounds F for all inputs in the domain H(x1,…,xp) < F(x1,…,xp) etc. The continuous relaxation of H is convex.
I can provide the objective function F, H, as well as a function B that returns a bound by solving the convex continuous relaxation minimization problem.
This should be all I need to provide a branch and bound algorithm.
Is there a flexible enough API somewhere that performs the branch and bound algorithm if I pass objective and bound functions as arguments?
I don’t imagine though why it would be particularly difficult to make a simple branch and bound API. Any branch and bound algorithm has the following 3 components:
A branching constraint generation function that given a relaxation problem and its optimal solution will generate n complementary constraints to branch upon.
A solver function that preprocesses and solves a problem possibly using the last solution obtained as a starting point.
A recursive generator that walks the search tree, queries for constraints to branch on, updates the lower and upper bounds on the original problem, and sends problems to the solver(s) once committed to a branch/choice.
The first 2 should be left to the user, so only the third item is what the API must have, doesn’t seem awfully difficult.
I think what makes the branch and bound algorithm particularly slippery is that it has many variants and options like choice of variables to branch on, branching constraints, tree walking strategy, randomness, restarts, and parallelism, but then most of these can be left to the user to decide with some defaults perhaps for certain classes of problems. I think this is also related to IntervalConstraintProgramming.jl and IntervalOptimisation.jl which I assume use different adaptations of a branch and bound algorithm, please correct me if I am wrong.
Are you aware of anyone working on such a package, or is it open if I want to give it a shot?
Hi Mohamed, I totally agree with you. Conceptually it shouldn’t be that hard to implement, yet on the other hand I know there are a lot of optimizations to be had, both in terms of coding and also heuristics which make or break the performance of the algorithm. I have been tempted to jump straight into implementing it myself, but I know this is a problem which others have thought about for a long time and so I was trying to see if there exists an already existing api which people have optimized.
A thread I found on or-exchange is relevant, discussing general branch and bound API, yet for my purposes at least all I am looking for is something simple. I supply an objective function and a bound function. The algorithm should traverse a tree but not go into subtrees for which the lower bound on the objective is greater than my current best.
I believe such an API is available in Haskell which appears to be exactly what I want.
I’m not aware of any such API in Julia, and based on the replies it seems there doesn’t seem to be, so if you’d like to have a crack at it then be my guest!
It seems most implementations of the branch and bound treat it as a tree and indulge in all the tree terminology like parent and child nodes, but I am not sure that’s the easiest way to view things, and hence program them, I think it might be adding a little more complexity than necessary. Anyways, I am of the mindset of recreating many of the popular optimization algorithms in Julia to make them more research-prone. For instance, I would never dare to mess with a single line of code in GLPK or CVXOPT but if written in pure Julia, I am totally up for playing around with them. But then I have to prioritize. I think logic/constraint programming and polynomial programming are on top of my list now, but branch and bound seems like a good Julia excerise, so I may start with it. Let’s see
I had the same feeling, that a tree based implementation might be overkill and that there is perhaps another way, but after some thought I wasn’t able to come up with anything better. Do you have any ideas for an alternative to tree based implementations? So far the best thing I have is a lazily constructed tree. It is important that the whole tree is not constructed.
I made a DFS proof of concept for MILPs with many assumptions and it worked. I am now rewriting it from scratch to be fully compatible with JuMP. It currently only supports linear constraint and variable bound choices but it shouldn’t be hard to extend to nonlinear constraints.
I am using a simple recursion, with a choices vector. The main complexity is in accounting for all possible choices that can be made when branching and their dependencies. Choices get commited and uncommitted when going deeper and backtracking respectively, and the main problem is shared. The generic framework is not long < 200 locs, but to specialize it for JuMP based and graph/networks based branch and bound, it is taking a while.
No, I haven’t considered that. I am not sure if that could be a problem for very deep trees. But very deep trees have little chance of being solved anyways, so a restart is probably a better strategy. I am not sure what the limit is before stack overflow happens. If that will be a problem, then a tree implementation is probably better.
Here is my current progress in BranchAndBound.jl. It has just enough code to make a minimum working example, but is by no means complete, your help would be appreciated!
I’m implementing one atm and started with the tree structure. It seems like there is some overhead though.
Maybe just having a list of nodes to branch on is more memory efficient.
Otherwise the tree structure seems to be the more natural implementation which might be easier to debug and might have more freedom to be used for different strategies like DFS or BFS.
Glad to see this thread still alive! I had and still have plans to change the implementation above to enable arbitrary search and node scoring strategies, and skip the recursive implementation which seems far from ideal.
For BFS or DFS, one way would be to go for a queue or a stack data structure respectively to keep track of leaf nodes at any one time. So basically each node will have a parent and children nodes associated, and they will be talking when updating upper or lower bounds. But each leaf node will also be a member of the queue or stack. So the nodes will be lazily truncated when you get to them if they are dominated by the best solution, otherwise they will be solved and branched on immediately. Then the new children will be added to the queue or stack and the parent node will have been removed.
I am planning to get back to this package sooner or later, but I am currently busy with a few other things, so that may take a while. If you want, you can also submit a PR with your implementation when it is ready to avoid duplicating the work. I have done some work in my package to make it possible to use for any user-defined branch and bound algorithm, but the actual branch and bound mechanism is still somewhat lacking. Good luck!
I need to code a BB algorithm that keeps track of all solutions whose cost is above a certain bound.
My question is how to warmstart before solving the LP relaxation? Ideally, I would to ask for the optimal dual basis and then plug it back before solving the relaxation of each node but this does not seem possible.
I believe that Coluna.jl may have some implementation for branch-and-bound which might be useful in other contexts (e.g. TreeSearchAlgorithm), but I have not studied it in detail.
