Introduction to Optimization Recitation 7 - Solutions

Introduction to Optimization Problem 1 – IP formulations Consider a production profit maximization problem with 4 production processes (running time expressed in hours) and 4 resource constraints: max 2 x1 + 3x2 + 5 x3 + 4 x4 3 s.t. x1 + x2 + 4 x3 + 4 x4 ≤ 40 (1) 4 2 x1 + x2 + 2 x3 + 3x4 ≤ 60 (2) x1 + 3x2 + 3x3 + x4 ≤ 70 3x1 + 2 x2 + 2 x3 ≤ 65 (3) ( 4) 0 ≤ x1 , x2 , x3 , x4 ≤ 100. Model the following additional production constraints, by introducing additional (possibly integer) variables and constraints. a) Suppose that there is an additional constraint that if process 1 is used, then process 2 cannot be used. We introduce a new variable y1, that would take the value 1 if process 1 is used, and 0 if process 1 is not used. The answer is to add the constraints: x1 ≤ 100 y1 , x2 ≤ 100(1 − y1 ), y1 ∈ {0,1}. b) Suppose that due to plant design, at least one of processes 1 and 2 has to run for at least 10 hours. We introduce two new variables y1 and y2, where yi is 1 if process i is used, and 0 otherwise. Then, the answer is to add the following additional constraints: x1 ≥ 10 y1 , x2 ≥ 10 y2 , y1 + y2 ≥ 1, y1 ∈ {0,1}, y2 ∈ {0,1}. c) Suppose that due to plant design, processes 1 and 2 can either run for 10 hours, or not run at all. Model the constraints that at least one of them has to run, but not both. Page 1 of 6 Again, we introduce two new variables y1 and y2, where yi is 1 if process i is used, and 0 otherwise. Then, the answer is to add the following additional constraints: x1 = 10 y1 , x2 = 10 y2 , y1 + y2 = 1, y1 ∈ {0,1}, y2 ∈ {0,1}. d) Suppose that due to plant design, each process can either run for 5 hours, or not run at all. Model the constraint that at most 3 processes can run. Model the constraint that exactly 3 processes have to run. Model the constraint that at least 3 processes have to run. We introduce the binary variables yi that take the value 1 if process i runs (for 5 hours), and 0 otherwise. Then, the solution is to add the following constraints (for the “at most” case): xi = 5 yi , i = 1,...,4, y1 + y2 + y3 + y4 ≤ 3, (*) yi ∈ {0,1}, i = 1,...,4. For the “exactly” case, substitute “=” instead of “≤” in constraint (*), and for the “at most” case, substitute “≥”. e) Suppose that due to plant design, process 4 can only run for 0, 4, 10, 15 or 20 hours. Model this constraint. We introduce 4 new binary variables, and the answer is to add the following constraints x4 = 4 y1 + 10 y2 + 15 y3 + 20 y4 , y1 + y2 + y3 + y4 ≤ 1, (*) yi ∈ {0,1}, i = 1,...,4. Note that the sign should be less than or equal to in constraint (*), to ensure that x4 can also take the value 0. The following points deal with additional specifics on the resource constraints: f) Suppose that instead of having to satisfy both constraint (1) and (2), it is enough to satisfy one of these constraints (it is still ok to satisfy both at the same time). Model this situation. We introduce a new variable y1 that equals 1 if constraint (1) is satisfied, and 0 otherwise. Also note that the left hand side of constraint (1) is at most 975, and that we already have 40 on the right hand side of constraint (1). Similarly, the LHS of (2) is at most 800, and we already have 60 on the RHS. Therefore, the answer is: Page 2 of 6 max 2 x1 + 3 x2 + 5 x3 + 4 x4 3 x1 + x2 + 4 x3 + 4 x4 ≤ 40 + 935(1 − y1 ) (1) s.t. 4 2 x1 + x2 + 2 x3 + 3x4 ≤ 60 + 740 y1 ( 2) x1 + 3x2 + 3x3 + x4 ≤ 70 3x1 + 2 x2 + 2 x3 ≤ 65 0 ≤ x1 , x2 , x3 , x4 ≤ 100, y1 ∈ {0,1}. (3) ( 4) g) Suppose that it is enough to satisfy any 2 of the 4 constraints (it is still ok to satisfy any 3, or all 4). Model this situation. We introduce 4 new binary variables yi, each equal to 1 if constraint (i) is satisfied, and to 0 otherwise. The answer is: max 2 x1 + 3 x2 + 5 x3 + 4 x4 3 s.t. x1 + x2 + 4 x3 + 4 x4 ≤ 40 + 935(1 − y1 ) 4 2 x1 + x2 + 2 x3 + 3x4 ≤ 60 + 740(1 − y2 ) x1 + 3x2 + 3 x3 + x4 ≤ 70 + 730(1 − y3 ) 3x1 + 2 x2 + 2 x3 ≤ 65 + 635(1 − y4 ) y1 + y2 + y3 + y4 ≥ 2 0 ≤ xi ≤ 100, yi ∈ {0,1} (1) ( 2) (3) ( 4) i = 1,...,4. h) Suppose that constraint (3) only needs to be satisfied if constraint (2) is not satisfied. Model this situation. Let y2 equal 1 if constraint (2) is satisfied, and 0 otherwise. The answer is: max 2 x1 + 3x2 + 5 x3 + 4 x4 3 (1) x1 + x2 + 4 x3 + 4 x4 ≤ 40 s.t. 4 2 x1 + x2 + 2 x3 + 3 x4 ≤ 60 + 740(1 − y2 ) (2) x1 + 3x2 + 3x3 + x4 ≤ 70 + 730 y2 3 x1 + 2 x2 + 2 x3 ≤ 65 0 ≤ x1 , x2 , x3 , x4 ≤ 100, y2 ∈ {0,1}. (3) (4) i) Suppose that constraint (4) only needs to be satisfied if none of the constraints (1, 2, 3) are satisfied. Model this situation. We introduce 3 new binary variables yi, each equal to 1 if constraint (i) is satisfied, and to 0 otherwise. The answer is: Page 3 of 6 max 2 x1 + 3 x2 + 5 x3 + 4 x4 3 x1 + x2 + 4 x3 + 4 x4 ≤ 40 + 935(1 − y1 ) s.t. 4 2 x1 + x2 + 2 x3 + 3 x4 ≤ 60 + 740(1 − y2 ) x1 + 3 x2 + 3 x3 + x4 ≤ 70 + 730(1 − y3 ) 3 x1 + 2 x2 + 2 x3 ≤ 65 + 635( y1 + y2 + y3 ) (1) ( 2) (3) ( 4) 0 ≤ xi ≤ 100, y j ∈ {0,1} i = 1,...,4, j = 1,...3. Problem 2 6 6 1 B 1 7 10 A 6 9. E 6 1 6 C 1 F 1 4 9 9 D 4 1 G 8 a) The LP: Minimize 7 x ab + 9 x ac + 4 x ac + xbe + 6 xbf + x cb + xcg + 9 x df + x dg + 6 xeh + 6 x fc + x fe + 9 x fg + 4 x gh + x hf subject to Page 4 of 6 H 2 xab + xac + xad = 10 − xab − xcb + xbe + xbf = −6 − xac − x fc + xcb + xcg = 0 − xad + xdf + xdg = 0 − xbe − x fe + xeh = 6 − xbf − xdf − xhf + x fc + x fe + x fg = 0 − xcg − x fg − xdg + x gh = −8 − xeh − x gh + xhf = 2 xij ≥ 0 for all xij b) All the decision variables will be integral. We note that our constraint matrix is a nodearc incidence matrix, and all basic feasible solutions (and therefore the optimal solution) will therefore be integral. More generally from lecture: In general, if there is at most one 1 and at most one –1 in any column of the constraint matrix (all other elements being 0), then every basic feasible solution is integer if the RHS is integral. Page 5 of 6 Problem 3 a) A this is a prime example of an assignment problem!!! b) Let Carol = 1,Jim =2, Margret =3 and Mike = 4. Let backstroke=1, breaststroke=2, butterfly=3 and freestyle=4. Then let xij =1 if swimmer i swims stroke j in the relay and 0 otherwise. We want to minimize the total time of the relay team, let cij represent the time of swimmer i for stroke j. We can then formulate the problem as: min s.t. 4 4 ∑∑ (c i =1 j =1 4 ∑x j =1 4 ∑x i =1 ij ij ij × xij ) =1 ∀i = 1,…,4 =1 ∀j = 1,…,4 xij ∈ {0,1} ∀i, j The optimal solution turns out to be letting Carol swim the butterfly, Jim the backstroke, Margret the freestyle and Mike the breaststroke, with the total time of 229.3 sec. Page 6 of 6