Operations Research Lecture 6: Integer Programming

1 Operations Research Lecture 6: Integer Programming notes taken by Kaiquan Xu@Business School, Nanjing University May 12th 2016. 1 Integer Programming (IP) formulations The Integer Programming (IP) is the same as the linear Programming (LP) problem except that some of the variables are restricted to take Integer values. IP is a powerful modeling framework that provides great flexibility for expressing discrete optimization problem. But the price for this flexibility is that IP is more difficult to solve than LP. Modeling techniques Binary choice An important use of a binary variable is to encode a choice between two alternatives. Example 1.

2 (The zero-one knapsack problem) We are given n items, the jth item has weight wj and its value is cj . Given a bound K on the weight that can be carried in a knapsack, we would like to select items to maximize the total value. In order to model this problem, xj is defined a binary variable, which is 1 if item j is chosen, and 0 otherwise. The problem can be formulated as follows: n P. max cj x j j=1. Pn w j xj K. j=1. xj {0, 1}, j = 1, .., n. Forcing constrains For some discrete problems, certain decisions are dependent. For example, decision A can be make only if decision B. has also been made. We can model this by using the constrain x y , if y = 0 (decision B is not made), then x = 0 (decision A cannot be made).

3 Example 2. (Facility location problems) Suppose we are given n potential facility locations and a list of m clients who need to be serviced from these locations. There is a fixed cost cj of opening a facility at location j, while there is a cost dij of serving client i from facility j. The goal is to select a set of facility locations and assign each client to 1. one facility, while minimizing the total cost. In order to model this problem, we define a binary decision variable yj for each location j, which is equal to 1 if facility j is selected, and 0 otherwise. We define a binary variable xij , which is equal to 1 if client i is served by facility j, and 0 otherwise.

4 The facility location problem is then formulated as follows: n P m P. P n max cj yj + dij xij j=1 i=1 j=1. Pn xij = 1, i, j=1. xij yj xij , yj {0, 1}, i, j. here, the forcing constrain xij yj captures the fact if there is no facility at location j (yj = 0), then client i cannot be served there, and we must have xij = 0. Relations between variables A constrain of the form n X. xj 1. j=1. where all variables are binary, implies that at most one of the variables xj can be one. If the constrain is of the form Pn xj = 1, then exactly one of the variable xj should be one. j=1. Disjunctive constrains Suppose we are given two constrains aT x b and cT x d, in which all of the components of a and c are nonneg- ative.

5 We want to model a requirement that at least one of the two constrains is satisfied. For achieving this, a binary variable y is defined, and the following constrains are imposed: aT x yb cT x (1 y)d, y {0, 1}. 2 Integer Programming (IP) methods Unlike LP problems, IP problems are very difficult to solve. No efficient general algorithm is known for their solution. Cutting plane methods Given the IP problem min cT x Ax = b (1). x 0. x Integer and its LP relaxation 2. min cT x Ax = b (2). x 0. The main idea in cutting plane methods is: first solve the LP relaxation 2 and find an optimal solution x . if x is Integer , then it is an optimal solution to 1.

6 If not, find an inequality that all Integer solutions to 1 satisfy, but x does not. We add this inequality to the LP problem to obtain a tighter relaxation, and we iterate this step. The performance of a cutting plane method depends critically on the choice of the inequality used to cut x . The Gomory cutting plane algorithm When solving the LP problem 2 with the simplex method, from the optimal tableau, we obtain the coefficients of the constraints xB + B 1 AN XN = B 1 b here, xB are the basic variables, and xN are nonbasic variables. Let a ij = (B 1 Aj )i and a i0 = (B 1 b)i , We only consider one equality from the optimal tableau, in which a i0 is fractional: X.

7 Xi + a ij xj = a i0. j N. Since xj 0 for all j, we have X X. xi + b . aij cxj xi + a ij xj = a i0. j N j N. Since xj should be Integer , we obtain X. xi + b . aij cxj b . ai0 c j N. This inequality is valid for all Integer solutions, but not satisfied by x . The reason is x i = a i0 , x j = 0 for all nonbasic j N , and b . ai0 c < a i0 (since a i0 was assumed fraction). Example 3. (Illustration of the Gomory cutting plane algorithm) we consider the IP problem. min x1 2x2. 4x1 + 6x2 9. x1 + x2 4. x1 , x2 0. x1 , x2 Integer We transform the problem in standard form min x1 2x2. 4x1 + 6x2 + x3 = 9. x1 + x2 + x4 = 4. x1 , x2 , x3 , x4 = 0. x1 , x2 , x3 , x4 Integer We solve the LP relaxation, and the optimal solution (in terms of the original variable) is x1 = (15/10, 25/10).

8 One 1 4. of the equations in the optimal tableau is x2 + 10 x3 + 10 x4 = 25. 10 . By applying the Gomory cutting plane algorithm, 3. Figure 1: Gomory Example we find the cut x2 2. We augment the LP relaxation by adding the constrain x2 + x5 = 2, x5 0, and we find the new optimal solution is x2 = (3/4, 2). One of the equations is the optimal tableau is 1 6 3. x1 x3 + x5 =. 4 4 4. We add a new Gomory cut x1 x3 + x5 0. which, in term of the original variables x1 , x2 , is 3x1 + 5x2 7. We add this constrain, and find the new optimal solution x3 = (1, 2), which is the optimal Integer solution. Branch and bound Branch and bound uses a divide and conquer approach to explore the set of feasible Integer solutions.

9 We partition the original problem into some subproblems, and try to compare the optimal solutions of subproblems. If subproblems are also very difficult to solve, we split them into further subproblems. For making the efficiency of this method, we also need to compute the lower bound of the corresponding subproblem- s, which usually are easy, for example, solving the corresponding LP relaxation. We also need to maintain an upper bound U , which could be the cost of the best feasible solution encountered so far. If the lower bound of a particular subproblem is larger than or equal to the U , then this subproblem need not to be considered further.

10 A generic branch and bound algorithm 1. Select an active subproblem Fi 2. If the subproblem is infeasible, delete it; otherwise, compute its lower bound b(Fi ) for the corresponding subprob- lem. 4. 3. If b(Fi ) U , delete the subproblem. 4. If b(Fi ) < U , either obtain an optimal solution to the subproblem, or break the corresponding subproblem into further subproblems, which are added to the list of active subproblems. If the optimal solution x to the LP relaxation is not Integer , we choose a component xi for which x i is not Integer and create two subproblems, by adding either of the constrains xi bx i c or xi dx i e Example 4. (Illustration of branch and bound) We solve the problem of Example 3 by branch and bound.