The Branch & Bound Method

The Branch & Bound method begins by finding the optimal solution in the absence of the integer constraints. If it happens that in this solution, the decision variables whose values are constrained to be integers already have integer values, then no further work is required.

If one or more integer variables have non-integral solutions, the Branch & Bound method chooses one such variable and "branches," creating two new subproblems where the value of that variable is more tightly constrained. For example, if integer variable A1 has the value 3.45 at the solution, then one subproblem will have the additional constraint A1 <= 3 and the other subproblem will add the constraint A1 >= 4. These subproblems are solved and the process is repeated, "branching" as needed on each of the integer decision variables, until a solution is found where all of the integer variables have integer values (to within a small tolerance).

Hence, the Branch & Bound method may solve many subproblems, each one a "regular" Solver problem. The number of subproblems may grow exponentially; the "bounding" part of the Branch & Bound method is designed to eliminate sets of subproblems that do not need to be explored because the resulting solutions cannot be better than the solutions already obtained. Obviously this may take a great deal of computing time.

Integer programming has many important applications. Many of them involve the use of integer decision variables that are further constrained to have values of either 0 or 1; these are called binary or 0-1 integer variables. Such variables may be specified in one step with the "bin" dropdown choice in the Add/Change Constraint dialogs. Binary integer variables can be used to represent yes/no decisions, such as whether a pipeline is open, or whether a facility is built at a certain location. For a discussion of applications of integer programming, please consult the references cited in the Introduction.