Introduction to Optimization Recitation 8 Solutions

Introduction to Optimizatio Problem 1 There are several ways to model this problem. It is difficult to say which one can be solved most efficiently without actually trying to solve it. Whatever way we choose to model it, we need to make sure that our objective function correctly models the revenues and cost for any gallon/degree relationship. Likewise we need to make sure that our decision variables “behave” correctly. Let w1 = 1 if we produce at least 200, 0 otherwise Let w2 = 1 if we produce at least 600, 0 otherwise Therefore, (x1 + x2 + x3) would represent the gallons produced 1/10x1 + 1/20x2 + 1/10x3 represents the temperature Maximize Subject to: -9.5(1/10x1 + 1/20x2 + 1/10x3) + .3(x1 + x2 + x3) 200w1 < x1 < 200 400w2 < x2 < 400w1 0 < x3 < 200w2 w1, w2 are binary Problem 2 Let xi,j = 1 if commercial of length i is assigned to block j and xi,j = 0 otherwise. Let yi = 1 if block i is used and yi = 0 otherwise. Then the appropriate formulation is Minimize z = y1 + y2 + y3 + y4 + y5 + y6 + y7 + y8 Subject to: 15x15,1+16x16,1+20x20,1+25x25,1+30x30,1+35x35,1+40x40,1+45x45,1+50x50,1+55x55,1≤60y1 15x15,2+16x16,2+20x20,2+25x25,2+30x30,2+35x35,2+40x40,2+45x45,2+50x50,2+55x55,2≤60y2 15x15,3+16x16,3+20x20,3+25x25,3+30x30,3+35x35,3+40x40,3+45x45,3+50x50,3+55x55,3≤60y3 15x15,4+16x16,4+20x20,4+25x25,4+30x30,4+35x35,4+40x40,4+45x45,4+50x50,4+55x55,4≤60y4 15x15,5+16x16,5+20x20,5+25x25,5+30x30,5+35x35,5+40x40,5+45x45,5+50x50,5+55x55,5≤60y5 15x15,6+16x16,6+20x20,6+25x25,6+30x30,6+35x35,6+40x40,6+45x45,6+50x50,6+55x55,6≤60y6 15x15,7+16x16,7+20x20,7+25x25,7+30x30,7+35x35,7+40x40,7+45x45,7+50x50,7+55x55,7≤60y7 15x15,8+16x16,8+20x20,8+25x25,8+30x30,8+35jx35,8+40x40,8+45x45,8+50x50,8+55x55,18≤60y8 k ∑x i =1 j ,i = 1 ∀ j ∈ {15, 16, 20, 25, 30, 35, 40, 45, 50, 55} All variables = 0 or 1 Problem 3 The formulation depends on how you interpreted the constraint logic. Let xi = 1 if we drill at site i, 0 otherwise. 10 Minimize ∑c x i =1 i i Subject to: (i) x2+x7+x6+x9 < 3 (interprets constraint as if(S2 and S7) then not (S6 and S9). The other interpretation is to have the following two constraints [x2+x7 +x9 < 2 and x2+x7+x6 < 2 ] (ii) x3+x6 < 1 x4+x6 < 1 (iii) x3 + x6 + x7 + x8 < 2 10 ∑x (iv) i =1 i = 5 we must look at leas 5 sites. xi - binary Problem 4: What in the world does fathomed mean? 1. When we cease to further branch on a node when performing branch and bound 2. (i) (ii) (iii) 3. (a) (b) Infeasible Solution to LP Relaxation Solution to LPR is less then or equal to incumbent(Assume Max) Solution to LPR is integral a1 + a2 < 15 There are many possibilities. One is c1 and c2 are negative and a1 + a2 >= 15 (which would yield a solution x6=1, x7=1). (c) There are many possibilities. One is: c1 and c2 are positive and c1 + c2 >=20 a1 + a2 = 15 The solution would be x6 = 1, x7 =1 at which the optimal value of the LP relaxation would be >= 35 (and thus worse than the incumbent since we’re minimizing). (d) There are many possibilities. One is: c1 and c2 positive; c1 + c2 < 19; c1 < c2 a1 + a2 >= 15; a1 < 15 The behavior of the LP relaxation would be as follows: Since we’re minimizing, set x6 = 1 since it has the smaller cost coefficient. Then set x7 to some fractional amount so that the a1x6 + a2x7 >= 15 constraint is satisfied (since a1 < 15 and can’t do it alone). Since c1 + c2 < 19, the objective value of the LP will be < 19 + 15 = 34, so the bound is better than the incumbent (since we’re minimizing). Thus, under these conditions, we would get a fractional solution and the node can’t be fathomed because the bound is better than the incumbent. Problem 5 Problem 6