Question

(Branch and bound can take exponential time) Consider the 0-1 programming problem Minimize Xn+]

subject to 2x1 + 2x2 + + 2xn + Xntl = n Xj {0,1}, j = 1,.n
Show that any branch and bound algorithm that uses linear programming relaxations to compute lower bounds, and branches by setting a fractional variable to either 0 or 1 will require the enumeration of an exponential number of nodes when n is odd.

Answer 1

A branch and bound algorithm that uses linear programming relaxations and branches by setting a fractional variable to either 0 or 1 will require the enumeration of an exponential number of nodes when n is odd in the 0-1 programming problem.

Step-by-step explanation:

In the 0-1 programming problem, we are trying to minimize the objective function Xn, subject to the constraint 2x1 + 2x2 + ... + 2xn + Xntl = n, where Xj is either 0 or 1.

A branch and bound algorithm that uses linear programming relaxations to compute lower bounds and branches by setting a fractional variable to either 0 or 1 will require the enumeration of an exponential number of nodes when n is odd.

Let's see why this is the case. When branching, we choose a variable with a fractional value and create two new subproblems by setting the variable to either 0 or 1.

Since the variables are binary, each branching creates 2 new subproblems. In each subproblem, the value of n decreases by 1, and we continue branching until we reach a feasible solution.

When n is odd, the branching process will reach a point where the remaining subproblem has n=1.

At this point, we have two subproblems, one with X1 = 0 and one with X1 = 1. We can see that these two subproblems are essentially the same, just with the value of X1 flipped. Therefore, the branching process will enumerate an exponential number of nodes when n is odd.