Optimization Methods - Exact Methods for IP

1 Outline Slide 1 Cutting plane methods Branch and bound methods 2 Cutting plane methods LP relaxation min s:t: cx Ax = b x
0 x integer
min s:t: cx Ax = b x
0: Slide 2 0 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 solutions satisfy, but x does not go to Step 1. � � Slide 3 � � 2.2 Example Let x be an optimal BFS to LP ralxation with at least one fractional basic variable. N : set of indices of the nonbasic variables. Is this a valid cut? X xj
1: � Slide 4 j N 2 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 N aij xj = ai0 : 2 Since xj
0 for all j , X X xi + baij cxj  xi + aij xj = ai0 : j N j N 2 2 Since xj integer, xi + X j N baij cxj  bai0 c: 2 Valid cut 2.4 Example x1 ; 2x2 ;4x1 + 6x2  9 x1 + 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 min s:t: 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 + 46 x5 = 43 : New Gomory cut x1 ; x3 + x5  0
New optimal solution is x3 = (1
2): 2 Slide 8 x2 3 . x1 2 .. - 3x1 + 5x 2 < 7 x2 x3 x2 < 2 1 0 1 2 3 4 x1 3 Branch and bound 1. 2. 3. 4. 5. Branching: Select an active subproblem Fi Pruning: If the subproblem is infeasible, delete it. Bounding: Otherwise, compute a lower bound b(Fi ) for the subproblem. Pruning: If b(Fi ) U , the current best upperbound, delete the subproblem. Partitioning: If b(Fi ) < U , either obtain an optimal solution to the subproblem Slide 9 (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 optimization problem. From the LP solution x , if there is a component xi which is fractional, we create two subproblems by adding either one of the constraints xi  bxi c
or xi
dxi 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. � Slide 10 � � � � 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 Prot=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 x = 1
i = 1
:: :
n + 1 x + x  1
8j
i =6 k j ij ij kj 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 j x = 1
i = 1
: ::
n + 1 P +1 �1 x  1
8j ij n ij i Which formulation is better for the problem? 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 problem 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 coecients to the right-hand-side. { Additional strengthening may be possible for integral variables using rounding.
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 7 6 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. P P min �1 c x �1 P s.t. : x = 1
j = 1
: ::
n
P�1 �1 x = 1
i = 1
:::
n
x 2 f0
1g: n i n i n j n j ij Slide 20 ij ij ij ij 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