Optimization Methods in Management Science Integer Programming Formulations

Integer Programming Formulations 2 Quote of the Day What chiefly characterizes creative thinking from more mundane forms are (i) willingness to accept vaguely defined problem statements and gradually structure them, (ii) continuing preoccupation with problems over a considerable period of time, and (iii) extensive background knowledge in relevant and potentially relevant areas. -- Herbert Simon Overview of lecture z First half of lecture: – more logical constraints – non-linearities z Second half of lecture – classic combinatorial problems • • • • set covering facility location graph coloring exam scheduling Logical Constraints with non-binary variables Variables: x1, x2, x3, are non-negative integers x1 ≤ 10 or x2 ≥ 25 or both Assume that x1 ≤ 100 . We need an upper bound. Create a variable w1 with the following properties: If w1 = 1, then x1 ≤ 10; If w1 = 0, then x2 ≥ 25; w1 = 0 or 1. x1 ≤ 9 + 91(1-w1) x2 ≥ 25 - 25w1 ww11==11 ww11==00 xx11≤≤ 99 100 xx11≤≤100 xx22≥≥ 00 25 xx22≥≥25 “Or-constraints” in general. ax ≤ b or cx ≥ d or both Let M1 and M2 be integers so that ax ≤ M1 and cx ≥ M2 in any feasible solution. Typically M1 is very large, and M2 is “very negative” If w2 = 1, then ax ≤ b; If w2 = 0, then cx ≥ d; w2 = 0 or 1. ax ≤ b + (M1 – b )(1-w2) cx ≥ d + (M2 –d) w2 w2 = 1 w2 = 0 ax ≤ b ax ≤ M1 cx ≥ M2 cx ≥ d Another example | x1 – x2 | ≥ 10 Assume x1 ≤ 100 and x2 ≤ 200. Translation: x1 – x2 ≥ 10 or x2 – x1 ≥ 10 Note: x1 – x2 ≥ -200 x2 – x1 ≥ -100 If w3 = 1, then If w3 = 0, then Fill in the table w3 = 1 w3 = 0 x1 – x2 ≥ 10 + x1 - x2 ≥ x1 - x2 ≥ x2 – x1 ≥ x2 – x1 ≥ x2 – x1 ≥ IP and piecewise linear functions. cost f(x) = 2 x if 0 ≤ x ≤ 3 f(x) = 9 – x if 4 ≤ x ≤ 7 f(x) = -5 + x if 8 ≤ x ≤ 9 Assume that x is integer valued. 0 3 7 9 x An NLP formulation How do we model the function f(x)? Later we will assume that f(x) is part of the objective function, and we will maximize it. Version 1: Create Binary Variables Step 1. Create three binary variables, w1, w2, and w3 w1 + w2 + w3 = 1 If 0 ≤ x ≤ 3 then w1 = 1 Almost works, but we need something else. If 4 ≤ x ≤ 7 then w2 = 1 If 8 ≤ x ≤ 9 then w3 = 1 wj ∈ {0, 1} for j = 1, 2, 3. Warning, this transformation will be challenging to follow the first time around. Version 2: Split x into three variables Step 2. Split x into three variables x1, x2, x3. If 0 ≤ x ≤ 3 then x1 = x; otherwise, x1 = 0. If 4 ≤ x ≤ 7 then x2 = x; otherwise, x2 = 0. If 8 ≤ x ≤ 9 then x3 = x; otherwise, x3 = 0. x = x1 + x2 + x3. Version 2 continued. Combine Steps 1 and 2. Transformation w1 + w 2 + w3 = 1 0 ≤ x1 ≤ 3 w 1 4w2 ≤ x2 ≤ 7 w2 8w3 ≤ x3 ≤ 9 w3 x = x1 + x2 + x3 f(x) = 2x1 + (9w2 – x2) + (-5w3 + x3) w1 + w2 + w3 = 1 If w1 = 1, then 0 ≤ x1 ≤ 3 If w1 = 0, then x1 = 0 If w2 = 1, then 4 ≤ x2 ≤ 7 If w2 = 0, then x2 = 0 If w3 = 1, then 8 ≤ x3 ≤ 9 If w3 = 0, then x3 = 0 x = x1 + x2 + x3 Last step z = 2x if 0 ≤ x ≤ 3 z= 9–x if 4 ≤ x ≤ 7 z = -5 + x if 8 ≤ x ≤ 9 Another non-linear function z = 2 x1 + 5x2 + f(x3) w1 + w 2 + w3 = 1 ⎧1 ⎪ f ( x3 ) = ⎨ 4 ⎪x ⎩ 3 if 0 ≤ x 3 ≤ 2 if 3 ≤ x 3 ≤ 6 if 7 ≤ x 3 ≤ 10 w1 + w 2 + w3 = 1 x3 = x31 + x32 + x32 x3 = x31 + x32 + x32 If w1 = 1, then 0 ≤ x31 ≤ 2 If w1 = 0, then x31 = 0 0 ≤ x31 ≤ 2 w1 If w2 = 1, then If w2 = 0, then x32 = 0 If w3 = 1, then If w3 = 0, then x33 = 0 ≤ x32 ≤ ≤ x33 ≤ z = 2 x1 + 5x2 + On representing non-linear functions z Integer programs can represent piecewise linear functions of one variable. They cannot represent non-linear functions with “curves.” z But they can nearly model non-linear functions with curves. One can create a piecewise linear function that is close to the original function. Mental Break 053 Chocolates Cleaver, Nooz, Ollie, and Tim have started a firm called 053 chocolates. Slogan: “053 chocolates are optimum.” Cleaver wants to ensure that everyone has easy access to the chocolates, and so requests that every district has an 053’s or is next to a district with an 053’s. Nooz wants to minimize the number of 053 stores to satisfy the “covering constraints.” How can we satisfy the both Nooz and Cleaver? 053 Chocolates 1 2 X 5 3 6 7 4 8X 11 9 12 X Minimize the number of stores needed. 13 10 X 14 15 X Locate 053 Chocolate stores so that each district has a store in it or next to it. 16 How do we represent this as an IP? xj = 1 if set j is selected xj = 0 otherwise Variables …++xx1616 Minimizexx11++xx22++… Minimize Objective s.t. xx11++xx22++xx44 ++xx55 ≥≥ 11 s.t. xx11++xx22++xx33++xx55++xx66 ≥≥ 11 x13 + x15 + x16 ≥ 1 xj ∈ {0, 1} for each j. Constraints Representation as Set Covering Problem 1 2 5 3 6 4 8 11 10 14 7 9 12 15 # Subset 1 {1, 2, 4, 5} 2 {1, 2, 3, 5, 6} 3 {2, 3, 6, 7} 16 {13, 15, 16} 13 16 Set covering Problem Let S = {1, 2, …, n}, and suppose Sj ⊆ S for each j. We say that index set J is a cover of S if Set covering problem: find a minimum cardinality set cover of S. Application to locating fire stations. Locating hospitals. Locating Starbucks and many non-obvious applications. ∪ j ∈J Sj = S More Integer Programming Formulations z Facility Location Problems z Graph Coloring z Exam Scheduling 053 Chocolates Location z z 6 customers. 3 possible locations for chocolate stores 1 2 B 4 3 C A 5 6 What is the best location for two chocolate stores so as to minimize total distance to customers? 1 2 3 4 5 6 A 4 1 4 4 1 4 B 2 2 6 2 2 6 C 6 2 2 6 2 2 Distances from possible chocolate stores to customers Formulation as an IP 1 Variables ⎧1 if store j is opened yj = ⎨ ⎩ 0 otherwise 33 2 B 4 A C 5 6 ⎧1 if costomer is is served by store j x ij = ⎨ ⎩ 0 otherwise Objective Constraints ∑∑ i j d ij x ij = 4 x1A + 2 x1B + 6 x1C + x2A + … x iA + x iB + x iC = 1 for i = 1 to 6 x ij ≤ y j for i = 1 to 6, and j = A, B, C y A + y B + yC = 2 x ij ∈ {0,1} for all i , j ; y j ∈ {0,1} for all j Warehouse Location Problem Open warehouses so as to minimize the total cost of doing business Location problems z z z z Locations: (Warehouses, or stores, or sites, or internet routers or … ) need to be opened Customers need to be served A customer cannot be served by a location unless the location is opened Variants: – there may be a cost for opening a location – customers in some problems may be served by more than one location – There may be a capacity on how much is stored at the warehouse. Graph Coloring Sedgwick Logan Weld Moffat Larimer Jackson Phillips Routt Morgan Yuma Boulder Grand Rio Blanco Adams Gilpin Denver Clear Arapahoe Creek Eagle Garfield Washington Jefferson Summit Elbert Kit Carson Douglas Pitkin Mesa Park Lake Lincoln Teller Cheyenne El Paso Delta 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? Graph Coloring Sedgwick Logan Moff at Weld Larimer Jackson Phillips Routt Mor gan Yuma Boulder Gr and Rio Blanco Adams Gilpin Denver Clear Ar apahoe Cr eek Eagle Garfield Washingt on Jeff erson Summ it Elbert Kit Carson Douglas Pitkin Mesa Park Lake Lincoln Teller Delt a Cheyenne El Paso Gunnison Chaff ee Fr emont Kiowa Montr ose Cr owley Our ay Pueblo Cust er Saguache San M iguel Pr owers Hinsdale Ot er o Dolor es Bent San Huerf ano Juan Alamosa Miner al Rio Gr ande Montezuma Baca Las Animas La Plat a Archulet a Conej os Costilla Here is a four coloring of the map. Graph Coloring Sedgwick Moffat Phillips Morgan Yuma Boulder Gr and Rio Blanco Clear Cr eek Eagle Garfield Summ it Washington Adams Gilpin Denver Jeff erson Ar apahoe Elbert Douglas G = (N, A) Logan Weld Larimer Jackson Routt N = {1, 2, 3, … n} set of counties Kit Carson Pitkin Mesa Lake Park Lincoln Teller Delt a Cheyenne El Paso Gunnison Chaff ee Fr emont Kiowa Montrose Cr owley Our ay San M iguel Cust er Saguache Hinsdale Pueblo Pr owers Otero Dolor es San Juan Mineral Alamosa Bent Huerf ano Rio Gr ande Montezuma La Plata Archulet a Conej os 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? The Integer Programming Formulation 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? 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. 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 ijk = ⎨ ⎩0 otherwise Minimize subject to ______________________ x ik + x jk ≤ y ijk + 1 for all i, j _________________________________ _________________________________ Summary of Integer Programming z Integer Programs can model an amazing number of different things. – linear constraints – logical constraints – non-linearities z It can be challenging to model z It can be challenging to solve z Next lectures: how to solve IPs