More Integer Programming Models

z Integer Programming Formulations 2 Announcement: at the end of lecture we will hand out a midsemester evaluation form 1 Comments on this Lecture Techniques for transforming combinatorial problems into integer programs. – piecewise linear functions – if-then constraints Application to multi-item auctions Applications to partitioning 2 IP and piecewise linear functions. cost 0 3 7 9 f(x) = 2 x if 0 ≤ x ≤ 3 f(x) = 9 – x if 3 ≤ x ≤ 7 f(x) = -5 + x if 7 ≤ x ≤ 9 x1 An NLP formulation Max f(x) + other stuff s.t. constraints 3 Transformation into an MILP f(x) = 2 x if 0 ≤ x ≤ 3 f(x) = 9 – x if 3 ≤ x ≤ 7 f(x) = -5 + x if 7 ≤ x ≤ 9 max 2x1 + (9y2 – x2) Max f(x) + other stuff + (-5y 3 + x3) s.t constraints 0 ≤ x1 ≤ 3y1 3y2 ≤ x2 ≤ 7y2 7y3 ≤ x3 ≤ 9y3 y1 + y2 + y3 = 1 y1 , y2 , y3 ∈ {0, 1} Let y1 = 1 if 0 ≤ x ≤ 3 Let y2 = 1 if 3 < x ≤ 7 Let y3 = 1 if 7 < x ≤ 9 y1, y2, y3 = 0 otherwise Let x1 = x if 0 ≤ x ≤ 3 Let x2 = x if 3 < x ≤ 7 Let x3 = x if 7 < x ≤ 9 x1, x2, x3 = 0 otherwise Replace x by x1 + x2 + x3 in all of the constraints. 4 Transformation into an MILP Let y1 = 1 if 0 ≤ x ≤ 3 Let y2 = 1 if 3 < x ≤ 7 Let y3 = 1 if 7 < x ≤ 9 Let x1 = x if 0 ≤ x ≤ 3 Let x2 = x if 3 < x ≤ 7 Let x3 = x if 7 < x ≤ 9 y1, y2, y3 = 0 otherwise x1, x2, x3 = 0 otherwise max 2x1 + (9y2 – x2) + (-5y3 + x3) s.t constraints Why the model is valid (Part 1): Suppose x is feasible for the NLP. 7y3 ≤ x3 ≤ 9y3 If 0 ≤ x ≤ 3, then set y1 = 1, and let y2 = y3 = 0. Let x1 = x, x2 = 0, and x3 = 0. Then x, y is feasible for the MILP, and its cost is 2x1, which is the same cost as for x. y1 + y2 + y3 = 1 y1 , y2 , y3 ∈ {0, 1} If 3 ≤ x ≤ 7, then set y1 = 0, y2 = 1, y3 = 0, etc. 0 ≤ x1 ≤ 3y1 3y2 ≤ x2 ≤ 7y2 5 Transformation into an MILP Let y1 = 1 if 0 ≤ x ≤ 3 Let y2 = 1 if 3 < x ≤ 7 Let y3 = 1 if 7 < x ≤ 9 Let x1 = x if 0 ≤ x ≤ 3 Let x2 = x if 3 < x ≤ 7 Let x3 = x if 7 < x ≤ 9 y1, y2, y3 = 0 otherwise x1, x2, x3 = 0 otherwise max 2x1 + (9y2 – x2) + (-5y3 + x3) s.t constraints 0 ≤ x1 ≤ 3y1 3y2 ≤ x2 ≤ 7y2 7y3 ≤ x3 ≤ 9y3 y1 + y2 + y3 = 1 y1 , y2 , y3 ∈ {0, 1} Why the model is valid (Part 2): Suppose x, y is feasible for the MILP. Suppose y1 = 1. Then y2 = y3 = x2 = x3 = 0. Let x = x1 in the NLP. Then the contribution of x in the NLP is 2x, which is the same contribution in the MILP. Suppose now that y2 = 1. Then ….. 6 On Fractional solutions. f(x) = 2 x if 0 ≤ x ≤ 3 f(x) = 9 – x if 3 ≤ x ≤ 7 f(x) = -5 + x if 7 ≤ x ≤ 9 Replace x by x1 + x2 + x3 in all of the constraints. max 2x1 + (9y2 – x2) In the current model, the yj is 0 or 1. Max f(x) + other stuff + (-5y 3 + x3) If we permitted fractions, then the s.t constraints objective would possibly increase. 0 ≤ x1 ≤ 3y1 3y2 ≤ x2 ≤ 7y2 For example, a feasible solution to the LP relaxation is x1 = y1 = 0. 7y3 ≤ x3 ≤ 9y3 y2 = y3 = .5; x2 = 2.5, x3 = 4.5. This leads to x = 7, but the objective y1 + y2 + y3 = 1 is 4 instead of 2. (The LP does not y1 , y2 , y3 ∈ {0, 1} model the NLP). 7 On representing non-linear functions z Integer programs can represent piecewise linear functions of one variable. z They can approximate non-linear functions of one variable. 8 Summary of subproblems modeled z z z Either-or constraints Fixed Charge Piecewise linear costs 9 Combinatorial Auctions z Outline – A brief discussion of auctions – multi-item auctions – combinatorial bidding 10 Auctions z 4 buyers (all unknown to each other) z One item: e.g., a Pete Rose 1964 rookie card z Evaluations by the buyers: – v1 = $850 – v2 = $730 – v3 = $1125 – v4 = $1350 In traditional auctions, bidder four would win the auction for around $1125 (assuming that bidder 3 bids up to his or her value and then stops). 11 Sealed Auctions: a single sealed bid from each person. z Evaluations by the buyers: – v1 = $850 – v2 = $730 – v3 = $1125 – v4 = $1350 Vickery Auction: a sealed bid, and the winner is the highest bidder, who then pays the second highest bid. For each person, the optimal strategy is to bid what something is worth. 12 Multi-item auctions z z They are usually run as a sequence of single item auctions. Potential Problem if bidders want to purchase a bundle of goods. 1 3 5 7 9 11 2 4 6 8 10 12 Suppose there are 7 bidders (bids in $ billion) v1( ) = 4, v2( 1 v5( 7 2 8 ) = 1, v3( 3 ) = 1, v4( 5 ) = 1, v6( 9 ) = 1, 10 v7( 11 4 6 12 ) = 1, ) = 1, 13 Exercise z Suppose that everyone knows everyone else’s true valuations. And suppose that the auction is sequential. z How much should bidders 1 and 2 bid on items 1 and 2? 1 3 5 7 9 11 2 4 6 8 10 12 Suppose there are 7 bidders (bids in $ billion) v1( ) = 4, v2( 1 v5( 7 2 8 ) = 1, v3( 3 ) = 1, v4( 5 ) = 1, v6( 9 ) = 1, 10 v7( 11 4 6 12 ) = 1, ) = 1, 14 Multi-item auctions and the exposure problem z Exposure problem showed up in 1998 Dutch spectrum auction, leading to large losses. 1 3 5 7 9 11 2 4 6 8 10 12 Either buyers overbid and make losses, or they do not bid aggressively. Next: Formulating as an integer program Allocate the goods so as to maximize the total value over all customers 15 Max s.t. Opt solution is to have xj = 1 for j = 2 to 6. x1 x2 x3 x4 x5 x6 x7 4 1 1 1 1 1 1 1 1 0 0 0 0 0 ≤ 1 0 1 0 0 0 0 0 ≤ 1 1 0 1 0 0 0 0 ≤ 1 0 0 1 0 0 0 0 ≤ 1 1 0 0 1 0 0 0 ≤ 1 0 0 0 1 0 0 0 ≤ 1 1 0 0 0 1 0 0 ≤ 1 0 0 0 0 1 0 0 ≤ 1 1 0 0 0 0 1 0 ≤ 1 0 0 0 0 0 1 0 ≤ 1 1 0 0 0 0 0 1 ≤ 1 0 0 0 0 0 0 1 ≤ 1 xj is 0 or 1 for j = 1 to 7. items 16 Class Exercise z Formulate the following problem as an IP – aij = 1 if item i is part of the j-th bid. – The value of the j-th bid is cj. – Objective: maximize revenue subject to no item is allocated more than once z Note: we are now considering actual bids rather than the values. 17 Other examples of combined value problems z Take-off and landing slots at airports z Selling airline tickets z Bidding for courses at U of Chicago’s business school z Buying transportation rights z Television airtime for advertising campaigns z and lots more 18 Graph Coloring Sedgwick Logan Moffat Weld Larimer Jackson Phillips Routt Morgan Yuma Boulder Grand Rio Blanco Adams Gilpin Arapahoe Creek Eagle Garfield Washington Denver Clear Jefferson Summit Elbert Kit Carson Douglas Pitkin Mesa Park Lake Lincoln Teller Delta Cheyenne El Paso Gunnison Chaffee Fremont Kiowa Montrose Crowley Ouray Pueblo Custer Saguache San Miguel Prowers Hinsdale Otero Dolores Bent San Huerfano Juan Alamosa Mineral Rio Grande Montezuma Baca Las Animas La Plata Archuleta Conejos Costilla This is a map of the counties in Colorado. Is it possible to color the counties with 4 colors so that no counties with a common border have the same color? 19 Graph Coloring Sedgwick Logan Moffat Weld Larimer Jackson Phillips Routt Morgan Yuma Boulder Grand Rio Blanco Adams Gilpin Clear Arapahoe Creek Eagle Garfield Washington Denver Jefferson Summit Elbert Kit Carson Douglas Pitkin Mesa Park Lake Lincoln Teller Delta Cheyenne El Paso Gunnison Chaffee Fremont Kiowa Montrose Crowley Ouray Pueblo Custer Saguache San Miguel Prowers Hinsdale Otero Dolores Bent San Huerfano Juan Alamosa Mineral Rio Grande Montezuma Baca Las Animas La Plata Archuleta Conejos Costilla Here is a four coloring of the map. 20 Graph Coloring Sedgwick Moffat Weld Larimer Jackson G = (N, A) Logan Phillips Routt Morgan Grand Rio Blanco Yuma Boulder Adams Gilpin Clear Creek Eagle Garfield Summit Washington Denver Jefferson Arapahoe Elbert Douglas N = {1, 2, 3, … n} set of counties Kit Carson Pitkin Mesa Lake Park Lincoln Teller Cheyenne El Paso Delta Gunnison Chaffee Fremont Kiowa Montrose Crowley Ouray San Miguel Hinsdale Pueblo Custer Saguache Prowers Otero Dolores San Juan Alamosa Mineral Bent Huerfano Rio Grande Montezuma La Plata Archuleta Conejos Costilla Las Animas A = set of arcs. (i, j) ∈ A if counties i and j are adjacent. Baca Exercise: write an integer program whose solution gives the minimum number of colors to color a map. Key choice: what are the decision variables? 21 An Exam Scheduling Problem The University of Waterford has to schedule 500 exams over two weeks. The objective is to schedule the exams in the fewest number of periods so that no person has to take two exams at the same time. G = (N, A) N = {1, 2, 3, … n} set of exams A = set of arcs. (i, j) ∈ A if a person needs to take exam i and exam j. How would one model this as an integer program? 22 Another Exam Scheduling Problem G = (N, A) N = {1, 2, 3, … n} set of exams There are m exam periods. A = set of arcs. (i, j) ∈ A if a person needs to take exam i and exam j. let cij = the number of persons who need to take exam i and exam j. Suppose that there are exactly m exam periods. Formulate the problem of minimizing the number of people in total who are taking two exams at the same time. 23 The IP formulation ⎧ 1 if exam i is scheduled in period k Let x ik = ⎨ ⎩0 otherwise ⎧ 1 if exams i and j are scheduled in period k Let y = ⎨ ⎩0 otherwise k ij Minimize subject to ______________________ x ik + x jk ≤ y ijk + 1 for all i, j _________________________________ _________________________________ 24 Warehouse location problem z n warehouses – cost fj of opening warehouse j z m customers – customer i has a “demand” of di – unit shipping cost cij of serving customer i via warehouse j. z Variables: – let yj = 1 if warehouse j is opened – Let xij = amount of demand for customer i satisfied via warehouse j. 25 A Warehouse Location Problem z z n customers. m warehouses. It costs fj to open warehouse j. 26 A Warehouse Location Problem z z determine what warehouses to open Assign customers to warehouses. – It costs cij to assign customer i to warehouse j. 27 Formulation as an integer program z Let yj = 1 if warehouse j is opened – Let yj = 0 otherwise z Let xij = 1 if customer i is assigned to warehouse j. – Let xij = 0 otherwise minimize Σi,j cijxij + Σj∈S fjyj Σj xij = 1 for each i xij ≤ yj for each i and j subject to customer i is assigned to a warehouse If customer i is assigned to warehouse j, then warehouse j must be open. xij and yj are binary 28 Suppose you knew which warehouses were open. S = set of open warehouses z xij = demand satisfied for customer i at warehouse j z yj = 1 for j in S, yj = 0 for j not in S. subject to: z customers get their demand satisfied z no shipments are made from an empty warehouse Σi,j cijxij + Σj∈S fj minimize Σj xij = di xij ≤ di xij = 0 if yj = 1 if yj = 0 and x ≥ 0 29 More on warehouse location z yj = 1 if warehouse i is opened yj = 0 otherwise z xij = flow from i to j Σi,j cijxij + Σj fi yi minimize subject to: z customers get their demand satisfied z each warehouse is either opened or it is not (no partial openings) z no shipments are made from an empty warehouse Σi xij = dj 0 ≤ yj ≤ 1 yj integral for all j. xij ≤ dj yi for all i, j and x ≥ 0 30 Two key aspects of using integrality in the model z Costs: we include the cost of the warehouse only if it is opened. Σi z fi yi Constraints: We do not allow shipping from warehouse j if it is not opened. – xij ≤ dj yi for all i, j 31 More on warehouse location z The above is a core subproblem occurring in supply chain management, and it can be enriched – more complex distribution system – capacity constraints – non-linear transportation costs – delivery times – multiple products – business rules – and more 32 Other Partitioning Problems z Lots of problems involve partitioning of a set z Often the problem has lots of additional complexities. – It may be challenging to write them as integer programs – But, usually an IP formulation is given z Next: slides from a talk to be given at the INFORMS practice meeting at the end of this month – Problems were solved using heuristics 33 Facility Location Problems Holmberg’s Problems. VLSN Search Heuristics Errors of Different Heuristics Average Error 0.002 0.0015 LH dfs bs 0.001 0.0005 0 1 50 2 85 3 150 4 200 Average Number of Customers 34 Weapon Target Assignment Problem Ahuja, Kumar, Jha and Orlin [2003] weapons targets error CPU time 20 40 0% 0.015 20 80 0% 0.031 40 40 0% 0.015 40 80 0% 0.078 40 120 0% 0.109 80 20 0% 0.156 80 80 0% 0.156 80 160 0% 0.219 80 320 0% 0.625 100 50 0% 0.437 100 100 0% 0.25 100 200 0% 0.609 200 100 0.01% 0.828 200 400 0% 2.516 • We varied the number of weapons from 10 to 200. • We varied number of targets from 5 to 400. • Almost all answers were optimal. • Running time for all but the largest problem was under 1 second. 35 Locomotive Scheduling Ahuja, Liu, Orlin, Sharma, and Shughart [2002] z We used integer programming, linear programming, and VLSN search for locomotive scheduling. z The total CPU time is 1 minute. z It reduced the number of locomotives needed by 25% over the currently used planning model. z Estimated savings: $400 million in capital equipment. 36 Airline Fleet Scheduling Ahuja et al. VLSN local Search Changes in fleeting contribution (in millions) Changes in though contribution (in millions) Changes in total contribution (in millions) Running time (sec.) FAM without maintenance 0.55 0 0.55 3 FAM with maintenance 3.84 0 3.84 10 ctFAM without maintenance -5.25 22.40 17.15 10 ctFAM with maintenance -0.94 27.80 26.86 9 37 Summary z Techniques for modeling as IPs – non-linear functions – logical constraints z Combinatorial Auctions z Partitioning Problems. 38 An Integer Program maximize 6x1 + 4x2 + 7x3 subject to 3x1 + 2x2 + 6x3 ≤ 150 4x1 + 3x2 + 4x3 ≤ 160 x1, x2 , x3 ≥ 0 and integral This integer program models linear costs of production. But sometimes, there are “fixed costs.” 39 Linear vs. Fixed Costs a linear cost cost = x cost x Fixed charges arise in manufacturing, and distribution cost cost = 0, if x = 0 x cost = 2 + x if x > 0 40 An Integer Program subject to 3x1 + 2x2 + 6x3 ≤ 150 4x1 + 3x2 + 4x3 ≤ 160 x1, x2 , x3 ≥ 0 and integral Suppose the profit for x1 is 6x1 - 100 if x1 > 0, and the profit is 0 if x1 = 0 Suppose the profit for x2 is 4x2 - 120 if x2 > 0, and the profit is 0 if x2 = 0 Suppose the profit for x3 is 7x1 - 100 if x3 > 0, and the profit is 0 if x3 = 0 41 The revised model with fixed costs Suppose the profit for x1 is 6x1 - 100 if x1 > 0, and the profit is 0 if x1 = 0 We will use the fact that x1 ≤ 40 in any feasible solution. This follows from constraint 2. profit for x1 = 6x1 - 100 y1 0 ≤ x1 ≤ 40 y1 y1 is 0 or 1 If x1 = 0, then y1 will be 0 in an optimal solution If x1 > 0, then y1 = 1, and the bound “x1 ≤ 40 y1” is redundant, since it was satisfied by any feasible solution. 42 The resulting integer program maximize 6x1 + 4x2 + 7x3 –120 y1 – 120 y2 – 100 y3 subject to 3x1 + 2x2 + 6x3 ≤ 150 4x1 + 3x2 + 4x3 ≤ 160 x1, x02 ≤, xx31 ≤ ≥ 40 0 y and integral 1 0 ≤ x2 ≤ 54 y2 0 ≤ x3 ≤ 25 y3 x1, x2 , x3 ≥ 0 and integral y1, y2 , y3 binary 43 An either or constraint maximize 6x1 + 4x2 subject to or x1 + 4x1 ≤ 6 5x1 + 2x1 ≤ 9 x1 = 2 x2 = 2 y1 = 0 or both x1, x2 ≥ 0 maximize subject to e.g. x1 = 2 x2 = 1 e.g. 6x1 + 4x2 + 7x3 x1 = 0 x2 = 3 y1 = 1 x1 + 4x1 ≤ 6 + 100 y1 5x1 + 2x1 ≤ 9 + 100 (1-y1) x1, x2 , x3 ≥ 0 y1 binary The constant M (100 in this case) should be chosen so large that the constraint is guaranteed to be satisfied if is RHS is M. x1 = 0 x2 = 3 e.g. x1 = 1 x2 = 1 x1 = 1 x2 = 1 y1 = ? 44 Representing piecewise linear functions This method is not in IMP cost 0 3 y1 7 y2 9 f1(x1) = 2 x1 if 0 ≤ x1 ≤ 3 f1(x1) = 9 – x1 if 3 ≤ x1 ≤ 7 f1(x1) = -5 + x1 if 7 ≤ x1 ≤ 9 x1 y3 Method: represent x1 as y1 + y2 + y3, and represent f1(x1) as the sum of linear functions of y1, y2, and y3. 45 Representing piecewise linear functions cost 0 3 y1 7 y2 9 f1(x1) = 2 x1 if 0 ≤ x1 ≤ 3 f1(x1) = 9 – x1 if 3 ≤ x1 ≤ 7 f1(x1) = -5 + x1 if 7 ≤ x1 ≤ 9 x1 y3 maximize z = 2 y1 – y2 + y3 0 ≤ y1 ≤ 3; 0 ≤ y2 ≤ 4; 0 ≤ y3 ≤ 2; if y1 < 3 then y2 = 0; if y2 < 4 then y3 = 0; Add the constraint: x1 = y1 + y2 + y3. Replace f(x1) Add constraints on y1 + y2 + y3 46 Representing piecewise linear functions Next: replace the if-then constraints COST = 2 y1 – y2 + y3 0 ≤ y1 ≤ 3; 0 ≤ y2 ≤ 4; if y1 < 3 then y2 = 0; This can be rephrased as: y1 ≥ 3 or y2 = 0; 0 ≤ y2 ≤ 4w1 ; y1 ≥ 3w1 ; w1 ∈ {0, 1} If w1 = 1, the constraints become 0 ≤ y2 ≤ 4 ; y1 ≥ 3; If w1 = 0, the constraints become y2 = 0 ; y1 ≥ 0. 47 Representing piecewise linear functions z = 2 y1 – y2 + y3 0 ≤ y1 ≤ 3; 0 ≤ y2 ≤ 4(1-w1) ; y1 ≥ 3w1 ; w1 ∈ {0, 1} 0 ≤ y3 ≤ 2; if y2 < 4 then y3 = 0; Exercise: model this using integer programming. 48 Concave Piecewise Linear Functions cost 0 2 Maximize 5 Σi fi(xi) subject to Ax = b x ≥ 0. 9 f1(x1) = 2x1 if 0 ≤ x1 ≤ 2 f1(x1) = 2 + x1 if 2 ≤ x1 ≤ 5 f1(x1) = 7 if 5 ≤ x1 ≤ 9 x1 A piecewise linear function is concave if the slopes of the pieces are decreasing. If fi(xi) is concave for all i, then the problem can be modeled as a linear program. 49 Concave Piecewise Linear Functions cost 0 2 y1 Max 5 y2 9 f1(x1) = 2x1 if 0 ≤ x1 ≤ 2 f1(x1) = 2 + x1 if 2 ≤ x1 ≤ 5 f1(x1) = 7 if 5 ≤ x1 ≤ 9 x1 y3 z = 2 y1 + y2 0 ≤ y1 ≤ 2; 0 ≤ y2 ≤ 3; 0 ≤ y3 ≤ 4; add the constraint x1 = y1 + y2 + y3. if y1 < 2 then y2 = 0; if y2 < 3 then y3 = 0; 50 Concave Piecewise Linear Functions Max z = 2 y1 + y2 0 ≤ y1 ≤ 2; 0 ≤ y2 ≤ 3; 0 ≤ y3 ≤ 4; cost if y1 < 2 then y2 = 0; if y2 < 3 then y3 = 0; 0 2 y1 5 y2 9 x1 x1 = y1 + y2 + y3. y3 y1, y2, and y3 appear only in the objective function and in the constraints above. We can drop the if-then constraints. If x1 = 7, then the unique optimal solution has y1 = 2, y2 = 3, and y3 = 2. What if x1 = 1? What if x1 = 4? 51