next up previous contents
Next: Cutting Plane Techniques Up: Solving Integer Programs Previous: Relationship to Linear Programming

Branch and Bound


We will explain branch and bound by using the capital budgeting example from the previous section. In that problem, the model is


The linear relaxation solution is tex2html_wrap_inline1649 with a value of 22. We know that no integer solution will have value more than 22. Unfortunately, since tex2html_wrap_inline1463 is not integer, we do not have an integer solution yet.

We want to force tex2html_wrap_inline1463 to be integer. To do so, we branch on tex2html_wrap_inline1463 , creating two new problems. In one, we will add the constraint tex2html_wrap_inline1657 . In the other, we add the constraint tex2html_wrap_inline1659 . This is illustrated in Figure 2.

Figure 2: First Branching

Note that any optimal solution to the overall problem must be feasible to one of the subproblems. If we solve the linear relaxations of the subproblems, we get the following solutions:

At this point we know that the optimal integer solution is no more than 21.85 (we actually know it is less than or equal to 21 (Why?)), but we still do not have any feasible integer solution. So, we will take a subproblem and branch on one of its variables. In general, we will choose the subproblem as follows:

In this case, we will choose the subproblem with tex2html_wrap_inline1659 , and branch on tex2html_wrap_inline1693 . After solving the resulting subproblems, we have the branch and bound tree in Figure 3.

Figure 3: Second Branching

The solutions are:

We now have a feasible integer solution with value 18. Furthermore, since the tex2html_wrap_inline1737 problem gave an integer solution, no further branching on that problem is necessary. It is not active due to integrality of solution. There are still active subproblems that might give values more than 18. Using our rules, we will branch on problem tex2html_wrap_inline1739 by branching on tex2html_wrap_inline1591 to get Figure 4.

Figure 4: Third Branching

The solutions are:

Our best integer solution now has value 21. The subproblem that generates that is not active due to integrality of solution. The other subproblem generated is not active due to infeasibility. There is still a subproblem that is active. It is the subproblem with solution value 21.65. By our ``round-down'' result, there is no better solution for this subproblem than 21. But we already have a solution with value 21. It is not useful to search for another such solution. We can fathom this subproblem based on the above bounding argument and mark it not active. There are no longer any active subproblems, so the optimal solution value is 21.

We have seen all parts of the branch and bound algorithm. The essence of the algorithm is as follows:

  1. Solve the linear relaxation of the problem. If the solution is integer, then we are done. Otherwise create two new subproblems by branching on a fractional variable.
  2. A subproblem is not active when any of the following occurs:
    1. You used the subproblem to branch on,
    2. All variables in the solution are integer,
    3. The subproblem is infeasible,
    4. You can fathom the subproblem by a bounding argument.

  3. Choose an active subproblem and branch on a fractional variable. Repeat until there are no active subproblems.

That's all there is to branch and bound! Depending on the type of problem, the branching rule may change somewhat. For instance, if x is restricted to be integer (but not necessarily 0 or 1), then if x=4.27 your would branch with the constraints tex2html_wrap_inline1791 and tex2html_wrap_inline1793 (not on x=4 and x=5).

In the worst case, the number of subproblems can get huge. For many problems in practice, however, the number of subproblems is quite reasonable.

For an example of a huge number of subproblems, try the following in LINGO:

    a /1..17/: x;

  max = -x0 + @sum(a: 2 * x);
  x0 + @sum(a: 2 * x) < 17;
  @for (a: @bin(x));
Note that this problem has only 18 variables and only a single constraint. LINDO looks at 48,619 subproblems, taking about 20 minutes on a Sun Sparc workstation, before deciding the optimal objective is 16. LINGO on a 16MHz 386 PC (with math coprocessor) looks at 48,000+ subproblems and takes about five hours. CPLEX on a Sun SPARC 10 takes about 50 seconds to examine 61,497 subproblems (counting those that are fathomed without solving the LP). The 100 variable version of this problem would take about tex2html_wrap_inline1799 subproblems or about tex2html_wrap_inline1801 years (at 1000 subproblems per second). Luckily, most problems take far less time.




next up previous contents
Next: Cutting Plane Techniques Up: Solving Integer Programs Previous: Relationship to Linear Programming

Michael A. Trick
Sun Jun 14 12:49:07 EDT 1998