Practice Problems Solutions

Optimization Methods in Management Science MIT 15.053, Spring 2013 Practical Problem Set, 2013 Problem 1 (IP Formulation) A combinatorial auction is an auction in which participants can place bids on sets of items, in­ stead of placing bids on individual items. A combinatorial auction is useful in many situations. For example, consider the problem of an airline company buying takeoff and landing slots at an airport: clearly, the value of a single slot may be small if the slot is taken by itself, but the value may be much larger if several slots can be bought at the same time, allowing the com­ pany to setup flight routes according to the desired timetable. Thus, the airport wants to sell its available slots to airline companies maximizing its own profit (i.e. the total value at which the slots are sold), allowing airlines to bid on sets of items and choosing the most profitable combination of bids among the received ones. Many other examples exist. In this problem, we study a simple formulation for a combinatorial auction. Consider a set composed by 5 items, labeled for simplicity: {1, 2, 3, 4, 5}. We auction off these items and receive the following bids, where each bid is placed on a subset of the items and assigns a value to the whole subset: • Bid 1: subset {1, 5} valued at 10. • Bid 2: subset {1, 2, 4} valued at 20. • Bid 3: subset {3} valued at 8. • Bid 4: subset {5} valued at 4. • Bid 5: subset {2, 4} valued at 15. • Bid 6: subset {2, 3, 4, 5} valued at 30. • Bid 7: subset {1, 2, 3} valued at 18. (a) (10 points) Formulate an integer program to choose the subset of bids that maximizes profit for the auctioneer, i.e. the total value for which the items are sold is maximum. We remark that each item can be sold at most once, and that bids cannot be split, that is: a bid for items {1, 2} can only be accepted if both item 1 and 2 are available. (Hint: this can be formulated as a set packing problem. Let xj be 1 if the j-th bid is accepted, 0 if it is not. These are all the variables we need!) Solution. max 10x1 + 20x2 + 8x3 + 4x4 + 15x5 + 30x6 + 18x7 s.t.: Item1: x 1 + x2 + x7 Item2: x 2 + x5 + x6 + x7 Item3: x 3 + x6 + x7 Item4: x 2 + x5 + x6 Item5: x 1 + x4 + x6 x1 , x2 , x3 , x4 , x5 , x6 , x7 ≤ ≤ ≤ ≤ ≤ ∈ 1 1 1 1 1 {0, 1}. ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ (b) (5 points) Suppose now that we are still auctioning off the set of items {1, 2, 3, 4, 5}, but now we have two copies each of items 1, 2, 3. In other words, the set of items for auctions looks like this: {1, 1, 2, 2, 3, 3, 4, 5}. 1 The set of received bids does not change, and each bid can only be accepted at most once. Modify your answer to the previous question to take into account the new availability of items. Solution. max 10x1 + 20x2 + 8x3 + 4x4 + 15x5 + 30x6 + 18x7 s.t.: Item1: x 1 + x2 + x7 Item2: x 2 + x5 + x6 + x7 Item3: x 3 + x6 + x7 Item4: x 2 + x5 + x6 Item5: x 1 + x4 + x6 x1 , x2 , x3 , x4 , x5 , x6 , x7 ≤ ≤ ≤ ≤ ≤ ∈ 2 2 2 1 1 {0, 1}. ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ (c) (10 points) Write an algebraic formulation for the problem of maximizing profit of the auctioneer, using the following notation: N = {1, . . . , n} is the set of auctioned items, each item is available with multiplicity λi ≥ 1 (i.e. there are λi copies of item i, i = 1, . . . , n), and we received b bids, where each bid consists of a subset Sj ⊆ N and a corresponding value pj , j = 1, . . . , b. Solution. max s.t.: i-th Item: ∀j = 1, . . . , b b j=1 pj xj ⎫ ⎪ ⎪ ⎪ ⎬ xj xj ≤ λi ⎪ ⎪ ⎪ ∈ {0, 1}. ⎭ j:i∈Sj Problem 2 (IP Formulation) We now analyze the problem of a firm trying to decide on the opening of several lockboxes. This problem is more complex than the previous one because we have to take into account the binary decisions of opening/not opening each potential lockbox, as well as an assignment problem to decide which regions should send their money to each lockbox. There are fixed costs for opening a lockbox, and there are opportunity costs for not opening a lockbox. This problem is based on an example from: G. Cornuéjols and R. Tütüncü, Optimization Methods in Finance. Consider a national firm that receives checks from all over the United States. Due to the vagaries of the U.S. Postal Service, as well as the banking system, there is a variable delay from when the check is postmarked (and hence the customer has met her obligation) and when the check clears (and when the firm can use the money). For instance, a check mailed in Boston sent to a Boston address might clear in just 2 days. A similar check sent to Los Angeles might take 6 days to clear. It is in the firm’s interest to have the check clear as quickly as possible since then the firm can use the money. In order to speed up this clearing process, firms open offices (called lockboxes) in different cities to handle the checks. 1 For the sake of formal correctness, this should not be called a set because items are allowed to appear more than once: it is instead a multiset. However, we will let simplicity win over formal correctness and use the term set anyway. So now you can’t say we always make things more complicated than they should. 2 For example, suppose we receive payments from 4 regions (West, Midwest, East, and South). The average daily value from each region is as follows: $600,000 from the West, $250,000 from the Midwest, $725,000 from the East, and $350,000 from the South. We are considering opening lockboxes in Los Angeles, Chicago, Boston, and/or Houston. Operating a lockbox costs $90,000 per year. Currently, all checks are mailed to Seattle, where the firm is based. We can assume that handling checks in Seattle does not cost extra money. The average days from mailing to clearing is given in Table ??. Which lockboxes should we open? From West Midwest East South L.A. 2 4 6 7 Chicago 4 2 5 5 Boston 6 5 2 6 Houston 6 5 5 3 Seattle 5 4 7 9 Table 1: Average clearing times for checks mailed from one region to L.A., Chicago, Boston, Houston or Seattle. First we must calculate the lost interest for each possible assignment. For example, if the West sends its checks to a lockbox in Boston, then on average there will be $3,600,000 (= 6 × $600 000) in process on any given day. Assuming a fixed investment rate of 4%, this corresponds to a yearly loss of $144,000. We can calculate the losses for the other combinations in a similar fashion; we obtain Table ??. From West Midwest East South L.A. 48 40 174 98 Chicago 96 20 145 70 Boston 144 50 58 84 Houston 144 50 145 42 Seattle 120 40 203 126 Table 2: Yearly opportunity costs (in thousands of dollars) for not being able to cash the checks immediately. We can open as many lockboxes as we need. Our goal is to determine the decision that minimizes total costs for the firm: how many lockboxes should be opened, and where. Note that this will require deciding which destination each region should mail checks to. To formulate the problem as an integer linear program, we will use the following variables. Let yj be a binary variable that is 1 if lockbox j is opened and 0 if it is not, j = 1, . . . , 4 (L.A., Chicago, Boston, Houston). Note that checks can always be handled in Seattle: there is no cost associated to opening a lockbox in Seattle. Let xij be 1 if region i sends its checks to lockbox j, i = 1, . . . , 4 (West, Midwest, East, South) and j = 1, . . . , 5 (j = 5 corresponding to Seattle). (a) Formulate the objective function of the problem, taking into account the cost of opening lockboxes and opportunity costs due to lost interest. As mentioned in the problem’s de­ scription, we can assume that checks can be handled in Seattle without having to pay extra for opening a lockbox there. Solution. We express everything in thousands of dollars. The objective function is: min 90x1 + 90x2 + 90x3 + 90x4 + 48y11 + 96y12 + 144y13 + 144y14 + 120y15 + 40y21 + 20y22 + 50y23 + 50y24 + 40y25 + 174y31 + 145y32 + 58y33 + 145y34 + 203y35 + 98y41 + 70y42 + 84y43 + 42y44 + 126y45 . 3 (b) Formulate the constraints that a region cannot send checks to a closed lockbox. How many of these constraints should we have? Solution. There are two natural ways of modeling this: ⎫ y11 + y21 + y31 + y41 ≤ x1 ⎪ ⎪ ⎬ y12 + y22 + y32 + y42 ≤ x2 y13 + y23 + y33 + y43 ≤ x3 ⎪ ⎪ ⎭ y14 + y24 + y34 + y44 ≤ x4 or: ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ y11 y21 y31 y41 y12 y22 y32 y42 y13 y23 y33 y43 y14 y24 y34 y44 x1 x1 x1 x1 x2 x2 x2 x2 x3 x3 x3 x3 x4 x4 x4 x4 ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ (c) Formulate the constraints that assign each region to the destination checks should be mailed to. Solution. y11 + y12 + y13 + y14 + y15 y21 + y22 + y23 + y24 + y25 y31 + y32 + y33 + y34 + y35 y41 + y42 + y43 + y44 + y45 = = = = 1 1 1 1 ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ (d) Put together the formulation discussed so far. Are we missing any constraints or do you think that this is enough? Solution. We put together the objective function and constraints to obtain the fol­ 4 lowing formulation: min Open Lockbox 1: Open Lockbox 2: Open Lockbox 3: Open Lockbox 4: Assign Region 1: Assign Region 1: Assign Region 1: Assign Region 1: ∀i = 1, . . . , 4 ∀i = 1, . . . , 4, j = 1, . . . , 5 90x1 + 90x2 + 90x3 + 90x4 +48y11 + 96y12 + 144y13 + 144y14 + 120y15 +40y21 + 20y22 + 50y23 + 50y24 + 40y25 +174y31 + 145y32 + 58y33 + 145y34 + 203y35 +98y41 + 70y42 + 84y43 + 42y44 + 126y45 y11 + y21 + y31 + y41 y12 + y22 + y32 + y42 y13 + y23 + y33 + y43 y14 + y24 + y34 + y44 y11 + y12 + y13 + y14 + y15 y21 + y22 + y23 + y24 + y25 y31 + y32 + y33 + y34 + y35 y41 + y42 + y43 + y44 + y45 xi yij ≤ ≤ ≤ ≤ = = = = ∈ ∈ x1 x2 x3 x4 1 1 1 1 {0, 1} {0, 1}. ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ The Open Lockbox constraints can be swapped for the alternative version given in Prob­ lem 3.b. This is enough to model the problem. (e) Go back to your answer to Problem 3.b. Come up with a different way of formulating the constraints that a region cannot send checks to a closed lockbox. Solution. The two possible versions are given in the answer to Part (b). (f) Suppose that operating 3 or more lockboxes (Seattle does not count) incurs an extra yearly cost of $50,000. This cost is on top of the $90,000 required to open each lockbox, and it applies if 3 or 4 lockboxes are opened. How can you model this constraint? Describe the additional constraints and, if needed, the additional variables required to model this constraint, as well as potential modifications to the objective function. Solution. We should introduce a binary variable w and the constraint x1 +x2 +x3 +x4 ≤ 2 + 2w. This implies that w = 1 is we operate 3 or more lockboxes. Then, we add 50w to the objective function. Problem 3 (Multiple choice) (a) Let the feasible region of the following integer program be called P: 1/2x + y ≤ 1 2x + y ≤ 2 x, y ≤ 0 x, y integer The feasible region P is equivalent to: 5 (i) x+y ≤1 x, y integer (ii) x≤1 y≤1 x, y integer (iii) Both (i) and (ii) (iv) Neither (i) nor (ii). Solution. Part (i) (b) Which of the following are possible for an integer program in which the objective is to maximize? Let ZIP be the optimal objective value of the integer program, assuming that it has an optimal solution. Let ZLP be the optimal objective value of the linear programming relaxation of the integer program, assuming that it has an optimal solution. Chooce all answers that are possible. (i) An integer program is infeasible but its linear programming relaxation has a feasible. solution (ii) An integer program is feasible but its linear programming relaxation is infeasible. (iii) ZIP = ZLP (iv) ZIP > ZLP (v) ZIP < ZLP Solution. Parts (i), (iii), and (v). (c) Let ZLP be the optimal solution for an LP relaxation of an integer program in which the objective is to maximize. Let ZGC be the optimal objective to the linear program obtained by adding a Gomory cut. Which of the following are possible? Chooce all that apply. (i) ZLP = ZGC (ii) ZLP > ZGC (iii) ZLP < ZGC . Solution. Parts (i) and (ii). (d) Let v be a node of the Branch and Bound tree of a 0–1 integer program in which the objective is to maximize. Let LP (v) be the optimal value for the LP relaxation of node v. Let c1 and c2 be the two children of node v in the tree. Assume that LP (v) is finite. Which of the following are possible? Choose all that apply. (i) The LP relaxations for c1 and c2 are both infeasible. 6 (ii) LP (v) = LP (c1 ) (iii) LP (v) > max{LP (c1 ), LP (c2 )} (iv) LP (v) < min{LP (c1 ), LP (c2 )} Solution. Parts (i), (ii) and (iii). Problem 4 (IP Formulation) (a) Write the following condition as integer programming constraints. At least one of the following two inequalities hold: x1 + x2 + x3 + x4 ≤ 4 3x1 − x2 − x3 + x4 ≤ 3 Write the equivalent IP constraints and define any new variables. Assume that xj ≥ 0 for each j = 1 to 4, and that each variable is required to be integer. Solution. x1 + x2 + x3 + x4 ≤ 4 + (1 − w)M 3x1 − x2 − x3 + x4 ≤ 3 + M w xj ≥ 0 and integer for j = 1, 2, 3, 4 w ∈ 0, 1 (b) Let ⎧ ⎪ ⎨10x f (x) = 500 ⎪ ⎩ 5x if 0 ≤ x ≤ 50, if 51 ≤ x ≤ 100, if x ≥ 101, Rewrite the following non-linear programming problem as an integer program. ⎫ min f (x) + 6y ⎪ ⎪ ⎬ s.t.: 1001x + 978y ≤ 27365 503x + 631y ≤ 16783 ⎪ ⎪ ⎭ x, y integer. Solution. min 10x1 + 500w2 + 5x3 + 6y s.t.: 1001x + 978y 503x + 631y w 1 + w2 + w3 x 1 + x2 + x3 0 ≤ x1 51w2 ≤ x2 x3 x1 , x2 , x3 w1 , w2 , w3 7 ≤ ≤ = = ≤ ≤ ≥ ≥ 27365 16783 1 x 50w1 100w2 101w3 0 and integer binary. ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ Problem 5 (Branch and Bound) We are using Branch-and-Bound to solve an Integer Program with an objective function in max­ imization form. All coefficients of the objective function are integer valued. We currently have the following Branch-and-Bound tree, where nodes are labeled N1 , . . . , N11 and the numbers below each node indicate the value of its LP relaxation. The incumbent solution was obtained in solving the LP at N4 . The optimal LP solution was feasible for the IP and had objective value 28. 32.2   30.5   28   31.5   29.8   30.5   28.2   29.8         ?   27.2   29.5   (a) Let v9 be the optimum value of the LP associated with node N9 . Select the best answer. (It is the answer that is correct and provides the most information.) (i) v9 ≤ 28.2 (ii) v9 = 30.5 (iii) v9 ≤ 30.5 (iv) v9 ≥ 28 Solution. Part (iii) (b) With the information that we currently have, what are the best upper and lower bounds that we can give on the value v ∗ of the optimal solution for the integer program? Solution. 28 ≤ v ∗ ≤ 30t (c) For each of the following nodes of the tree, say whether it is active (A) or fathomed (F) or whether there is not enough information (NEI) to know. (Write “A”, “F” or “NEI” next to each node.) Solution. N4 F N5 A N8 F 8 N10 F N11 A Problem 5 (Gomory Cut) After solving the LP relaxation of an Integer Program by the Simplex algorithm, we obtain the following optimal Simplex tableau: Basic (−z) x1 x2 x5 x1 x2 1 1 x3 -2.4 2.65 0.24 0.3 x4 -0.25 -0.2 0.4 -4.3 x5 1 Rhs -26.6 3.3 4.5 0.9 Compute the Gomory cut from the first row of the Simplex tableau . Show the steps required for the derivation of the cut. Solution. By rounding down the coefficients and the RHS, we obtain x1 + 2x3 − 1x4 ≤ 3, By subtracting this inequality from the first row of the tableau, we get the following Gomory cut: 0.65x2 + 0.8x3 ≥ 0.3. 9