University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

376

Pages:

3
Author:

Cheyenne Villegas

Introduction to Optimization Problem 1: 30 Points Consider the following IP: max z = 14x1 + 18x2 s.t. -x1 + 3x2 ≤ 6 7x1 + x2 ≤ 35 x1, x2 ≥ 0; x1, x2 integer The optimal tableau for this IP’s linear programming relaxation is: z x y s1 s2 1 0 0 56 30 11 11 0 0 1 7 1 22 22 0 1 0 3 −1 22 22 Use the cutting plane algorithm to solve this IP. RHS 126 7 9 2 2 Problem 2: Branch and Bound and Cutting Planes 40 Points Consider the following capital budgeting problem: We have a set of six possible investments with the following characteristics: Investment 1 2 3 4 5 NPV Added $32 $44 $24 $16 $38 Cash Required $10 $14 $8 $6 $12 6 $22 $8 We want to find the optimal set of investments that maximizes the total NPV while limiting the amount of initial investment to $27. a. Formulate an integer program that yields the optimal set of investments that maximizes net present value. b. Solve the LP relaxation for this problem using the accompanying spreadsheet (ps8.xls). c. Perform two levels of the branch and bound algorithm. First branch on x1, then branch on x2. Choose x1 = x2 =1 and x3 = x4 = x5 = x6 = 0 as your initial incumbent solution. Draw a tree that shows all of the nodes investigated with the resulting LP relaxation objective and decision variable values. Which of the nodes investigated can be fathomed? What is our incumbent solution at this point? d. By adding inequalities (cuts) (at least 4), what can you conclude about the optimal integer objective value? Show what constraints you add and the resulting solution to the LP relaxation. (Add the constraints in Excel and use solver – you do not need to turn in the Excel sheet.) e. Explain in your own words how cutting plain techniques (as in part d) can make branch and bound algorithms more efficient? (1-3 sentences). f. Use Excel to solve for the optimal integer solution (constrain the decision variables to be integer). What is the optimal solution? Problem 3 Gomory cuts 30 Points Consider the following Cutting Plane Algorithm: Step 1: Find the optimal tableau for the IP’s linear programming relaxation. If all variables in the optimal solution are integer then STOP. Otherwise, go to step 2. Step 2: Pick a constraint in the LP relaxation optimal tableau whose right-hand side has the fractional part closest to ½. For this constraint create a Gomory cut. (This will eliminate the current LP relaxation solution from the solution set.). Add the new constraint to the problem (this leads to a new slack variable). Step 3: Use Excel pivoting to find the optimal solution to the LP relaxation with the cut as an additional constraints. Go to step 1. Now consider the following IP: Maximize z = 2x1 + 2x2 Subject to 2x1 + x2 ≤ 5 -4x1 +4x2 ≤ 5 x1, x2 ≥ 0, x1, x2 integer. Solving the LP relaxation of the problem we got the following final tableau z 1.00 0.00 0.00 x1 0.00 1.00 0.00 x2 0.00 0.00 1.00 s1 4/3 1/3 1/3 s2 1/6 -1/12 1/6 RHS 15/2 5/4 5/2 Solve the IP problem with the Cutting-Plane-Algorithm, the initial tableau is set up in ps8.xls. In each iteration you will need to add the cut to the initial tableau and re-pivot.