Application Example of theBranch and Bound AlgorithmConsider the Capital Budgeting problem (which, as we already know, is structurally identicalto the Knapsack problem, so we can use either name). Its formulation is this:max Z =nXi=1pixiSubject tonXi=1cixi≤ Cxi∈ {0, 1}, i = 1, . . . , nLet us try to find the exact solution with the Branch and Bound (B&B) algorithm. In orderto do it, we need to handle the following issues.1. Transforming the formulationIn B&B we considered the optimization taskmaxx∈Bf(x).This does not have any constraint and seeks for the optimum over all binary vectors ofdimension n. In contrast, our problem do es have a constraint and seeks for the optimumonly over those binary vectors that satisfy the constraint.To handle this difference, we need to transform our constrained task into an unconstrainedone. It can be done by the method that is often called penalty function method. It is based onthe idea that we can substitute a constraint by modifying the objective function, such thatwe “penalize” those vectors that violate the constraint. In this way, we can do the searchover all vectors (with the modified objective function), because when a global, unconstrainedoptimum is found, the “penalty” does not allow it to be taken at a vector that violates theconstraint.Specifically, in our case, we can do the following. The original objective function wasf(x) =nXi=1pixi.1Let the modified objective function beef(x) =Pni=1pixiifPni=1cixi≤ C0 ifPni=1cixi> C.We can observe that whenever a vector x satisfies the constraint,ef(x) = f(x) holds. On theother hand, if x violates the constraint, thenef(x) = 0. Since the maximum we are lookingfor is positive1, therefore, this positive maximum ofef(x) cannot be taken on a vector thatviolates the constraint, asef(x) = 0 for those vectors, by definition. Thus, if we solvemaxx∈Bef(x)by B&B, then the optimum provides us with the optimum of the Knapsack problem.2. Finding a good upper bound functionIn B&B we use an upper bound function Uk(b) that provides an upper bound on the partialoptimum Fk(b) (see the Lecture Note about B&B).What will be Fk(b) is our case? If we fix the first k variables at values b1, . . . , bk∈ {0, 1},then we get the following new Knapsack problem:maxnXi=k+1pixi+kXi=1pibiSubject tonXi=k+1cixi≤ C −kXi=1cibixi∈ {0, 1}, i = k + 1, . . . , nFk(b) is the optimum of this task. How do we get the upper bound function Uk(b)? We cantake the LP relaxation of this ILP, replacing the constraint xi∈ {0, 1} by 0 ≤ xi≤ 1. Thus,Uk(b) is the optimum solution of the LP1Assuming each item alone fits in the knapsack, since we can a priori exclude those that do not.2Uk(b) = maxnXi=k+1pixi+kXi=1pibiSubject tonXi=k+1cixi≤ C −kXi=1cibi0 ≤ xi≤ 1, i = k + 1, . . . , n3. Fast computation of the upper b ound functionThe whole B&B approach makes sense only if we can compute the upper bound functionsignificantly faster than the original task. In our case we face the problem: how do we quicklysolve the above LP that defines Uk(b)? Fortunately, this LP has a special structure: it is thecontinuous version of the Knapsack problem. By continuous we mean that xi∈ {0, 1} hasbeen replaced by 0 ≤ xi≤ 1. For such a continuous knapsack it is known that the optimumcan be found by a fast greedy algorithm, as follows.Order the variables according to decreasing pi/ciratio. Let us call it preference ordering.The most preferred variable is the one with the highest pi/ciratio. Consider the variablesstarting by the most preferred one, and assign them the value 1, as long as it is possiblewithout violating the budget constraint. (Note that in the considered subproblem the budgetis C −Pki=1cibi. If it happens to be negative, then there is no solution to the subproblem,and we can represent it by Uk(b) = −1, so that this branch of the search tree will surelybe cut down.) When we cannot continue assigning 1 anymore without violating the budget,then assign a fractional value to the next variable, so that the remaining part of the budget,if any, is exactly used up. The remaining variables, if any, take 0 as their value. One canprove that this value assignment gives the optimum solution to the continuous Knapsackproblem. Therefore, we have a fast way of computing Uk(b).Thus, we have all the ingredients to apply B&B. We aim at computingmaxx∈Bef(x)and whenever the algorithm calls for Uk(b), we can compute it by the fast algorithm
View Full Document
Unlocking...