Lecture 13: Exact Methods for IP

15.093: Optimization Methods Lecture 13: Exact Methods for IP 1 Outline Slide 1 � Cutting plane methods � Branch and bound methods 2 Cutting plane methods LP relaxation min s:t: c0x Ax � b x�0 x integer; min s:t: c0x Ax � b x � 0: 2.1 Algorithm � Solve the LP relaxation. Let x� be an optimal solution. � If x� is integer stop; x� is an optimal solution to IP. � If not, add a linear inequality constraint to LP relaxation that all integer Slide 2 Slide 3 solutions satisfy, but x� does not; go to Step 1. 2.2 Example � Let x� be an optimal BFS to LP ralxation with at least one fractional Slide 4 basic variable. � N : set of indices of the nonbasic variables. � Is this a valid cut� X xj � 1: j 2N 2.3 The Gomory cutting plane algorithm � Let x� be an optimal BFS and B an optimal basis. � xB + B�1AN xN � B�1b: � � � � � aij � B �1Aj i , ai0 � B �1b i : 1 Slide 5 � xi + X j 2N aij xj � ai0 : � Since xj � 0 for all j , X X xi + baij cxj � xi + aij xj � ai0 : j 2N j 2N � Since xj integer, � Valid cut xi + X j 2N baij cxj � bai0 c: 2.4 Example min x1 � 2x2 s:t: �4x1 + 6x2 � 9 x 1 + x2 � 4 x1 ; x2 � 0 x1 ; x2 integer: We transform the problem in standard form min x1 � 2x2 s:t: �4x1 + 6x2 + x3 �9 x1 + x2 + x4 � 4 x1 ; : : :; x4 � 0 x1 ; : : :; x4 integer. LP relaxation: x1 � (15�10; 25�10). � � Gomory cut Slide 6 Slide 7 1 x � 25 : x2 + 101 x3 + 10 4 10 x2 � 2: � Add constraints x2 + x5 � 2, x5 � 0 � New optimal x2 � (3�4; 2): � One of the equations in the optimal tableau is x1 � 14 x3 + 64 x5 � 43 : � New Gomory cut x1 � x3 + x5 � 0; � New optimal solution is x3 � (1; 2): 2 Slide 8 x2 3 . x1 .. - 3x1 + 5x 2 < 7 x2 2 x3 x2 < 2 1 0 1 2 3 4 x1 3 Branch and bound 1. 2. 3. 4. 5. Branching: Select an active subproblem Pruning: If the subproblem is infeasible, delete it. Bounding: Otherwise, compute a lower bound ( ) for the subproblem. Pruning: If ( ) � , the current best upperbound, delete the subproblem. Partitioning: If ( ) , either obtain an optimal solution to the subproblem Slide 9 Fi b Fi b Fi U b Fi � U (stop), or break the corresponding problem into further subproblems, which are added to the list of active subproblem. 3.1 LP Based � Compute the lower bound b(F ) by solving the LP relaxation of the discrete Slide 10 optimization problem. � From the LP solution x� , if there is a component x�i which is fractional, we create two subproblems by adding either one of the constraints xi � bx�i c; or xi � dx�i e: Note that both constraints are violated by x� . � If there are more than 2 fractional components, we use selection rules like maximum infeasibility etc. to determine the inequalities to be added to the problem � Select the active subproblem using either depth-�rst or breadth-�rst search strategies. 3.2 Example max 12x1 + 8x2 + 7x3 + 6x4 s:t: 8x1 + 6x2 + 5x3 + 4x4 � 15 x1; x2; x3; x4 are binary: 3 Slide 11 Objective value=22.2 x1=1, x2=0, x3=0.6, x4=1 x3=1 x3=0 Objective value=22 Objective value=22 x1=1, x2=0.5, x3=0, x4=1 x1=1, x2=0, x3=1, x4=0.5 Objective value=22.2 x1=1, x2=0, x3=0.6, x4=1 x3=1 x3=0 Objective value=22 Objective value=22 x1=1, x2=0.5, x3=0, x4=1 x1=1, x2=0, x3=1, x4=0.5 x4=1 x4=0 Objective value=21.66 Objective value=22 x1=1, x2=0.33, x3=1, x4=0 x1=0.75, x2=0, x3=1, x4=1 LP relaxation Slide 12 max 12x1 + 8x2 + 7x3 + 6x4 s:t: 8x1 + 6x2 + 5x3 + 4x4 � 15 x1 � 1; x2 � 1; x3 � 1; x4 � 1 x1 ; x2; x3; x4 � 0 LP solution: x1 � 1; x2 � 0; x3 � 0:6; x4 � 1 Pro�t�22:2 3.2.1 Branch and bound tree 3.3 Pigeonhole Problem � There are n + 1 pigeons with n holes. We want to place the pigeons in the holes in such a way that no two pigeons go into the same hole. � Let xij � 1 if pigeon i goes into hole j , 0 otherwise. � Formulation 1: P � 1; i � 1; : : : ; n + 1 xij + xkj � 1; 8j; i 6� k j xij 4 Slide Slide Slide Slide 13 14 15 16 Slide 17 Objective value=22.2 x1=1, x2=0, x3=0.6, x4=1 x3=1 x3=0 Objective value=22 Objective value=22 x1=1, x2=0.5, x3=0, x4=1 x1=1, x2=0, x3=1, x4=0.5 x4=1 x4=0 Objective value=21.66 Objective value=22 x1=1, x2=0.33, x3=1, x4=0 x1=0.75, x2=0, x3=1, x4=1 x1=1 x1=0 Objective value=21 Infeasible x1=0, x2=1, x3=1, x4=1 � Formulation 2: P � 1; : : : ; n + 1 xij � 1; 8j i�1 Which formulation is better for the problem� j xij � 1; Pn+1 i Slide 18 � The pigeonhole problem is infeasible. � For Formulation 1, feasible solution xij � n1 for all i; j . O(n3) constraints. Nearly complete enumeration is needed for LP-based BB, since the prob lem remains feasible after �xing many variables. � Formulation 2 Infeasible. O(n) constraints. � Mesage: Formulation of the problem is important! 3.4 Preprocessing � � � An e�ective way of improving integer programming formulations prior to and during branch-and-bound. Logical Tests { Removal of empty (all zeros) rows and columns; { Removal of rows dominated by multiples of other rows; { strengthening the bounds within rows by comparing individual variables and coe�cients to the right-hand-side. { Additional strengthening may be possible for integral variables using round ing. Probing : Setting temporarily a 0-1 variable to 0 or 1 and redo the logical tests. Force logical connection between variables. For example, if 5x + 4y + z � 8; x; y; z 2 f0; 1g, then by setting x � 1, we obtain y � 0. This leads to an inequality x + y � 1. 5 Slide 19 1 2 4 3 5 6 7 4 Application 4.1 Directed TSP 4.1.1 Assignment Lower Bound Given a directed graph G � (N; A) with n nodes, and a cost cij for every arc, �nd a tour (a directed cycle that visits all nodes) of minimum cost. min s.t. : Pn Pn �1 Slide 20 Pn i j �1 cij xij � 1; j � 1; : : : ; n; Pin�1 x � 1; i � 1; :::; n; j �1 ij xij 2 f0; 1g: xij Branching:Set one of the arcs selected in the optimal solution to zero. i.e., add Slide 21 constraints of the type \xij � 0" to exclude the current optimal solution. 4.2 Improving BB � � � � � Better LP solver Use problem structure to derive better branching strategy Better choice of lower bound b(F ) - better relaxation Better choice of upper bound U - heuristic to get good solution KEY: Start pruning the search tree as early as possible 6 Slide 22