Branch and Bound (BB) is a search method for Mixed Integer Linear Programming (MILP) and for Mixed Integer Nonlinear Programming (MINLP). MILPs and MINLPs can be solved by enumerating search trees; BB is a method for pruning those search trees to decrease solution time.
BB reduces the search space by considering a subproblem at a node of the search tree, relaxing the resulting MILP or MINLP (in discrete space) to an LP or NLP (in continuous space), and then solving the relaxed problem. The solution of the relaxed problem, depending on its form, may provide an upper or a lower bound to the entire problem. Comparing upper and lower bounds for the master problem to the solution for a relaxed problem at a node will let us know if any of the nodes children may potentially provide an optimal solution. If that is a possibility, the children nodes are then evaluated in the same way. If it is not, the node and all its children are removed from consideration.
A. Land and A. Doig , An Automatic Method of Solving Discrete Programming Problems, Econometrica 28 (1960), 497.
G. Nemhauser and L. Wolsey. "Integer and Combinatorial Optimization" Wiley, New York, 1988
L.T. Biegler, I.E. Grossmann, and A.W.Westerberg. "Systematic Methods of Chemical Process Design" Prentice Hall, New Jersey, 1997
E. Lee and J. Mitchell, Branch-and-Bound Methods for Integer Programming
Eric W. Weisstein et al. "Branch and Bound Algorithm." From MathWorld--A Wolfram Web Resource
We intend to implement a parallelized version of BB. For the purposes of this project we will consider only MILPs; this will allow us to satisfy the relaxed subproblems efficiently. A later extension to allow MINLPs would be implementable by altering the algorithm used to evaluate the subproblems.
The program will be used to solve one MILP rapidly, as opposed to solving multiple MILPs simultaneously. We intend to design the program such that an extension to solving multiple MILPs in parallel would not require any major program revisions.
We will make use of already existing code to solve the relaxed subproblems. The key issues in this project are therefore:
Other, less critical, issues include:
All material on this page copyright Jane E. Valentine, 2005