IP Formulation Guide–Abbreviated

IP Reference guide for integer programming formulations. for 15.053 and 15.058 This document is intended as a compact (or relatively compact) guide to the formulation of integer programs. For more detailed explanations, see the PowerPoint tutorial on integer programming. The following are techniques for transforming a problem described logically or in words into an integer program. In most cases, the transformation is the simplest to describe. Unfortunately, simplest is not the same as "best." It is widely accepted that the best integer programming formulations are those that result in fast solutions by integer programming solvers. In general, these are the integer programs for which the linear programming relaxation provides a good bound. Section 1. Subset selection problems. Often, models are based on selecting a subset of elements. For example, in the knapsack problem, one wants to select a subset of items to put into a knapsack so as to maximize the value while not going over a specified weight. Or one wants to select a subset of potential products in which to invest. Or, one has a set of different integers, and one wants to select a subset that sums to a value K. In these cases, it is typical for the integer variables to be as follows: ⎧⎪ 1 xi = ⎨ ⎩⎪ 0 if element i is selected otherwise. Example: knapsack/capital budgeting. In this example, there are six items to select from. Item Cost Value 1 5 16 2 7 22 3 4 12 4 3 8 5 4 11 6 6 19 Problem: choose items whose cost sums to at most 14 so as to maximize the utility. maximize Formulation: 16x1 + 22x2 + 12x3 + 8x4 + 11x5 + 19x6 5x1 + 7x2 + 4x3 + 3x4 + 4x5 + 6x6 ≤ 14 subject to xi ∈{0,1} In general: for i = 1 to 6. Maximize the value of the selected items such that the weight is at most b. Ci = value of item i for i = 1 to n. ai = weight of item i for i = 1 to n. b = bound on total weight. n maximize ∑c x i=1 i i n subject to ∑a x i=1 i i ≤b xi ∈{0,1} for i = 1 to n. Covering and packing problems. In some selection problems, each item is associated with a subset of a larger set. The larger set is usually referred to as the ground set. For example, suppose that there is a collection of n sets 51, ", 5n where for i = 1 to n 5i is a subset of the ground set {1, 2, 3, ", m}. Associated with each set 5i is a cost Ci. ⎧⎪ 1 if i ∈S j ⎩⎪ 0 otherwise. Let aij = ⎨ ⎧⎪ 1 if set S j is selected ⎩⎪ 0 otherwise. Let x j = ⎨ The set paCking problem is the problem of selecting the maximum cost subcollection of sets, no two of which share a common element. The set Covering problem is the problem of selecting the minimum cost subcollection of sets, so that each element i E {1, 2, ", m} is in one of the sets. Maximize subject to ∑ ∑ n j=1 n cjxj a x j ≤ 1 for each i ∈{1,...,m} j=1 ij x j ∈{0,1} Minimize subject to ∑ ∑ n j=1 n Set Packing Problem for each j ∈{1,...,n}. cjxj a x j ≥ 1 for each i ∈{1,...,m} j=1 ij x j ∈{0,1} Set Covering Problem for each j ∈{1,...,n}. For example, consider the following map of the counties of Colorado. Figure 1. The counties of Colorado. Suppose that we want to select a minimum cardinality subset C of counties such that each county either was in C or shared a common boundary with a county in C. In this case, we would let 5j = {j} U {i: county i shares a boundary with county j}. We let Cj = 1 for each j. We would then solve the min cost covering problem. Here is a related problem. Select the largest subset CC of counties such that no two counties of CC share a common border. We refer to this problem as P1. Although P1 is a set packing problem (as you shall soon see) it is not the set packing problem defined on the sets S1, S2, ", Sn . To see why not, consider the following example. Suppose that county 1 bordered on county 2, which bordered on county 3, but that counties 1 and 3 had no common border. Then one can include both county 1 and county 3 in CC. But 2 E S1 n S3, and so it would not be possible to select S1 and S3 for the set packing problem. Problem P1 can be formulated as follows: Maximize ∑ subject to xi + x j ≤ 1 n j=1 xj x j ∈{0,1} whenever aij = 1 (i.e., i ∈S j ) Problem P1 for each j ∈{1,...,n}. Section 2. Modular arithmetic. In this very brief section, we show how to constrain a variable x to be odd or even, and we show how to constraint x to be a mod(b). (That is, there is an integer q such that a + qb = x.) In each case, we need to add a new variable w, where w � 0 and integer. Constraint. IP Constraint x is odd. x - 2w = 1. x is even. x - 2w = 0. x = a (mod b) x - bw = a. Table 1. Modular arithmetic formulations. Section 3. Simple logical constraints. Here we address different logical constraints that can be transformed into integer programming constraints. In the first set, we describe the logical constraints in terms of selection of items from a subset. Logical Constraint. IP Constraint If item i is selected, then item j is also selected. xi - xj : 0 Either item i is selected or item j is selected, but not both. xi + xj = 1 Item i is selected or item j is selected or both. xi + xj � 1 If item i is selected, then item j is not selected. xi + xj : 1 If item i is not selected, then item j is not selected. -xi +xj : 0 At most one of items i, j, and k are selected. xi + xj + xk : 1 At most two of items i, j, and k are selected. xi + xj + xk : 2 Exactly one of items i, j, and k are selected. xi + xj + xk = 1 At least one of items i, j and k are selected. xi + xj + xk � 1 Table 2. Simple constraints involving two or three binary variables. Restricting a variable to take on one of several values. Suppose that we wanted to restrict x to be one of the elements {4, 8, 13}. This is accomplished as follows. x = 4 w1 + 8 w2 + 13 w3 w1 + w2 + w3 = 1 wi E {0, 1} for i = 1 to 4. If we wanted to restrict x to be one of the elements {0, 4, 8, 13}, it suffices to use the above formulation with the equality constraint changed to "w1 + w2 + w3 : 1." Section 4. Other logical constraints, and the big M method. Binary variables that are 1 when a constraint is satisfied. We next consider binary variables that are defined to be 1 if a constraint is satisfied, and 0 otherwise. In each case, we need bounds on how much the constraint could be violated in a solution that satisfies every other constraint of the problem. Example 1. ⎧⎪ 1 w= ⎨ ⎩⎪ 0 if x ≥ 1 if x = 0. In this example, x is an integer variable. And suppose that we know x is bounded above by 100. (We may know the bound on x because it is one of the constraints of the problem. We may also know the bound of 100 on x because it is implied by one or more of the other constraints. For example, suppose that one of the constraints was "3x + 4y + w : 300." We could infer from this constraint that 3x : 300 and thus x : 100. Equivalent constraint: w : x : 100w. w E {0,1}. In any feasible solution, the definition of w is correct. If x � 1, then the first constraint is satisfied whether w = 0 or w = 1, and the second constraint forces w to be 1. If x = 0, then the first constraint forces w to be 0, and the second constraint is satisfied. ⎧⎪ 1 if x ≥ 7 Example 2. w= ⎨ otherwise. ⎪⎩ 0 Again, we assume here that x is an integer variable, and that x is bounded above by 100. Equivalent constraints: x : 7 - 7(1-w) x : 6 + 94 w w E {0,1}. In any feasible solution, the definition of w is correct. If x � 7, then the first constraint is satisfied whether w = 0 or w = 1, and the second constraint forces w to be 1. If x : 6, then the first constraint forces w to be 0, and the second constraint is satisfied. Big M: example 1. ⎧⎪ 1 w= ⎨ ⎪⎩ 0 if x ≥ 7 otherwise. Here we assume that x is an integer variable that is bounded from above, but we donCt specify the bound. Equivalent constraints: x : 7 - M(1-w) x : 6 + Mw w E {0,1}, where M is chosen sufficiently large. In this way, we donCt concern ourselves with the value of the bound. We just write M. In fact, we could have written 7 instead of M in the first constraint, and it would have also been valid. But writing big M means not having to think about the best bound. The disadvantage of this approach is that the running time of the integer programming algorithm may depend on the choice of M. Choosing M very large (e.g., M = 1 trillion) will lead to valid formulations, but the overly large value of M may slow down the solution procedure. ⎧⎪ 1 if x ≥ a w= ⎨ otherwise. ⎪⎩ 0 Here we assume that x is an integer variable that is bounded from above, but we donCt specify the bound. Big M: example 2. Equivalent constraints: x : a - M(1-w) x : (a-1) + Mw w E {0,1}, where M is chosen sufficiently large. In any feasible solution, the definition of w is correct. If x � a, then the first constraint is satisfied whether w = 0 or w = 1, and the second constraint forces w to be 1. If x : a-1, then the first constraint forces w to be 0, and the second constraint is satisfied. ⎧⎪ 1 if x ≤ a w= ⎨ otherwise. ⎪⎩ 0 Here we assume that x is an integer variable that is bounded from above, but we donCt specify the bound. Big M: example 3. Equivalent constraints: x 5 a - M(1-w) x ≥   � (a+1) + Mw w E {0,1}, where M is chosen sufficiently large. In the case that w depends on an inequality constraint involving more than one variable, the previous two transformations can modified in a straightforward manner. ⎧ ⎪ 1 w= ⎨ ⎪⎩ 0 Big M: example 4. Here we assume that bound. ∑ Equivalent constraints: n if ∑ n ax ≤b i=1 i i otherwise. a x is integer valued and is bounded from above, but we donCt specify the i=1 i i ∑ ∑ n a x ≤ b + M (1− w). i=1 i i n a x ≥ b + 1− Mw. i=1 i i w ∈{0,1}. In any feasible solution, the definition of w is correct. If ∑ n a x ≤ b, , then the first constraint is i =1 i i satisfied whether w = 0 or w = 1, and the second constraint forces w to be 1. If the first constraint forces w to be 0, and the second constraint is satisfied. ∑ n a x ≥ b + 1, , then i=1 i i At least one of three inequalities is satisfied. Suppose that we wanted to model the logical constraint that at least one of three inequalities is satisfied. For example,   x1  +  4x2  +  2x4  ≥  7      or    3x1  -­‐  5x2  ≤    12      or  2x2  +  x3  ≥    6.     We  then  create  three  new  binary  variables  w1,  w2,  and  w3  and  reformulate  the  above  constraint  as   the  following  system  of  logical,  linear,  and  integer  constraints.       If  w1  =  1,  then  x1  +  4x2  +  2x4  ≥  7.   If  w2  =  1,  then  3x1  -­‐  5x2  ≤    12.   If  w3  =  1,  then  2x2  +  x3  ≥    6.   w1  +  w2  +  w3  ≥    1.   wi  ∈  {0,1}      for  i  =  1  to  3.     This  above  system  of  constraints  is  equivalent  to  the  following.       x1  +  4x2  +  2x4       ≥  7  -­‐  M(1-­‐w1)   ≤    12  +  M(1-­‐w2)   3x1  -­‐  5x2       2x2  +  x3     ≥    6    -­‐  M(1-­‐w3)   w1  +  w2  +  w3     ≥  1.        (Using  an  equality  would  also  be  valid.)   wi  ∈  {0,1}      for  i  =  1  to  3.     At  least  one  of  two  inequalities  is  satisfied.     In  the  case  of  two  inequalities,  it  suffices  to  create  a  single  new  variable  w.      For  example,  suppose   that  we  want  to  satisfy  the  following  logical  condition.    At  least  one  of  the  following  two  constraints   is  satisfied:   x1  +  4x2  +  2x4  ≥  7      or    3x1  -­‐  5x2  ≤    12.     This  logical  condition  is  equivalent  to:       x1  +  4x2  +  2x4       ≥      7  -­‐  Mw   3x1  -­‐  5x2     ≤    12  +  M(1-­‐w)     w  ∈  {0,1}         Section  5.    Fixed  costs     Here  we  consider  an  integer  program  in  which  there  are  fixed  costs  on  variables.    For  example,   consider  the  following  integer  program:     Maximize f (x1 ) + f 2 (x2 ) + f3 (x3 ) 2x1 + 4x2 + 5x3 ≤ 100 subject to x1 + x2 + x3 ≤ 30     10x1 + 5x2 + 2x3 ≤ 204 xi ≥ 0 and integer for i = 1 to 3.   where   ⎧ 52x − 500 if x ≥ 1 ⎪ 1 1   f1 ( x1 ) = ⎨ 0 if x =0 1 ⎩⎪ ⎧ 30x − 400 if x ≥ 1 ⎧ 20x − 300 ⎪ ⎪ 2 2 3  ,   f 2 (x2 ) = ⎨ ,   f3 (x3 ) = ⎨ 0 if x = 0 0 ⎪⎩ 2 ⎩⎪ if x3 ≥ 1 if x3 = 0 .   The IP formulation is as follows: Maximize subject to 52x1 − 500w1 + 30x2 − 400w2 + 20x3 − 300w3 2x1 + 4x2 + 5x3 ≤ 100 x1 + x2 + x3 ≤ 30 10x1 + 5x2 + 2x3 ≤ 204 xi ≤ Mwi for i = 1 to 3 xi ≥ 0 and integer for i = 1 to 3. The constraint xi : Mwi forces wi = 1 whenever xi > 0. The model may look incorrect because it permits the possibility that xi = 0 and wi = 1. It is true that the IP model allows more feasible solutions than it should. However, if xi = 0 in an optimal solution, then wi = 0 as well because its objective value coefficient is less than 0. Because the integer program gives optimal solutions, if xi = 0, then wi = 0. Section 6. Piecewise linear functions. Integer programming can be used to model functions that are piecewise linear. For example, consider the following function. ⎧ 2x ⎪ y = ⎨ 9− x ⎪ ⎩ −5 + x if 0 ≤ x ≤ 3 if 4 ≤ x ≤ 7 if 8 ≤ x ≤ 9. One can model y in several different ways. Here is one of them. We first define two new variables for every piece of the curve. ⎧⎪ 1 w1 = ⎨ ⎪⎩ 0 if 0 ≤ x ≤ 3 otherwise. ⎧⎪ x x1 = ⎨ ⎪⎩ 0 ⎧⎪ 1 w2 = ⎨ ⎩⎪ 0 if 4 ≤ x ≤ 7 otherwise. ⎪⎧ 1 w3 = ⎨ ⎩⎪ 0 if 8 ≤ x ≤ 9 otherwise. ⎪⎧ x2 = ⎨ ⎪⎩ ⎪⎧ x3 = ⎨ ⎪⎩ if 0 ≤ x ≤ 3 otherwise. x if 4 ≤ x ≤ 7 0 otherwise. x if 8 ≤ x ≤ 9 0 otherwise. We complete the model as follows. IP formulation y = 2x1 + 9w2 - x2 -5w3 + x3 0 : x1 : 3w1 4w2 : x2 : 7w2 8w3 : x3 : 9w3 w1 + w2 + w3 = 1 x = x1 + x2 + x3 wi E {0, 1} for i = 1 to 3. For any choice of w1, w2, and w3, the variables x and y are correctly defined. Section 7. The traveling salesman problem In this section, we give the standard model for the traveling salesman problem. It has an exponential number of constraints, which may seem quite unusual for an integer programming model. We explain how it can be implemented so as to be practical. We assume that there are n cities, and that Cij denotes the distance from city i to city j. In this model, the following are the variables: ⎧⎪ 1 if city i is immediately followed by city j on the tour xij = ⎨ ⎩⎪ 0 otherwise. The formulation is as follows: n Minimize n ∑∑ c x i=1 j=1 n subject to ∑x j=1 ij n ∑x i=1 ∑ ij i∈S , j∈N \S ij ij =1 for all i = 1 to n =1 for all j = 1 to n xij ≥ 1 for all S ⊂ {1,2,...,n} with 1 ≤ S ≤ n − 1 xij ∈{0,1}, for all i, j = 1 to n. The first set of constraints ensures that there is some city that follows city i in the solution. The second set of constraints ensures that there is some city that precedes city j in the solution. Unfortunately, there are not enough constraints to ensure that the solution is a tour. For example, a feasible solution to the first two sets of constraints for the six city problem consists of x12 = x23 = x31 = 1, and x45 = x56 = x64 = 1. This "solution" to the first two sets of constraints corresponds to the cycles 1-2-3-1 and 4-5-6-4. A tour should be one cycle only. The third set of constraints guarantees the following. For any non-empty subset 5 of cities with �S� � n, there must be some city not in 5 that follows some city that is in 5. This set of constraints is known as the subtour elimination Constraints. With all of the constraints listed above, every feasible solution corresponds to a tour. Implementation details. Suppose that one wanted to solve the linear programming relaxation of the TSP� that is, we solve the problem obtained from the above constraints if we drop the integrality constraints, and merely require that xij � 0 for each i and j. (We wonCt deal with solving the integer program here.) We refer to this linear program as LP�. At first it appears that there is no way of solving LP� for any large values of n, say n > 100. For any TSP instance with more than 100 cities, there are more than 2100 different subtour elimination constraints. Listing all of the constraints would take more than all of the computer memory in the entire world. Instead, LP� is solved using a "constraint generation approach." LP(0) is obtained from LP� by dropping all of the subtour elimination constraints. An optimal solution x0 is obtained for LP(0). If x0 is feasible for LP�, then it is also optimal for LP�. If not, then some subtour elimination constraint that x0 violates is identified and added to LP(0), resulting in LP(1). ItCs not obvious how one can determine a subtour elimination constraint that is violated, but there are efficient approaches for finding a violated subtour elimination constraint. An optimal solution x1 is obtained for LP(1). If x1 is feasible for LP�, then it is also optimal for LP�. If not, then some subtour elimination constraint that x1 violates is identified and added to LP(1), resulting in LP(2). This process continues until there is an optimal solution for LP(k) for some k that is feasible for LP� and hence optimal for LP�. Or else, the solver takes so much time, that it is stopped before reaching optimality. In practice, the technique works quite well, and finds an optimal solution for LP� in a short amount of time.