15.081J/6.251J Introduction to Mathematical Programming Lecture 25: Exact Methods for Discrete Optimization� � � � � 1 Outline Slide 1 • Cutting plane methods • Branch and bo und methods 2 Cutting plane methods Slide 2 ′ min c x s.t. Ax = b x ≥ 0 x integer, LP relaxation ′ min c x s.t. Ax = b x ≥ 0. 2.1 Algorithm Slide 3 • Solve the LP relaxation. Let x ∗ be an optimal solution. • If x ∗ is integer stop; x ∗ is an o ptimal 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. 2.2 Example Slide 4 • Let x ∗ be an optimal BFS to LP ralxation with at least one fra c tional basic variable. • N: set of indices of the nonbasic variables. • Is this a valid cut? xj ≥ 1. j∈N 2.3 The Gomory cutting plane algorithm Slide 5 • Let x ∗ be an optimal BFS and B an optimal basis. • xB + B−1AN xN = B−1b. • aij = B−1Aj , ai0 = B−1b i . i1� � � � • xi + aij xj = ai0. j∈N • Since xj ≥ 0 for all j, xi + ⌊aij ⌋xj ≤ xi + aij xj = ai0. j∈N j∈N • Since xj integer, xi + ⌊aij ⌋xj ≤ ⌊ai0⌋. j∈N • Valid cut 2.4 Example Slide 6 min x1 − 2x2 s.t. −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). Slide 7 • 1 1 25 x2 + x3 + x4 = . 10 10 10 • Gomory cut x2 ≤ 2. • Add constraints x2 + x5 = 2, x5 ≥ 0 • New optimal x2 = (3/4, 2). • One of the equations in the optimal tableau is 1 6 3 x1 − x3 + x5 = . 4 4 4 • New Gomory cut x1 − x3 + x5 ≤ 0, • New optimal solution is x3 = (1, 2). Slide 8 2... x2 < 2 - 3x 1 + 5x2 < 7 1 2 3 43 2 1 0 x2 x1 x1 x2 x3 3 Branch and bound Slide 9 1. Branching: Select an active subproblem Fi 2. Pruning: If the subproblem is infeasible, delete it. 3. Bounding: Otherwise, compute a lower bound b(Fi) for t he subproblem. 4. Pruning: If b(Fi) ≥ U, the current best upperbound, delete t he subproblem. 5. Partitioning: If b(Fi) < U, either obtain an optimal solution to the subproblem (stop), or break the corresponding problem into further subproblems, which are added t o the list of active subp roblem. 3.1 LP Based Slide 10 • 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 o ne of the constraints ∗ ∗ xi ≤ ⌊xi ⌋, or xi ≥ ⌈xi ⌉. Note that both constraints are vio lated 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-first or br eadth-first search strategies. 3.2 Example Slide 11 max 12x1 + 8x2 + 7x3 + 6x4 s.t. 8x1 + 6x2 + 5x3 + 4x4 ≤ 15 x1, x2, x3, x4 are binary. 3� Objective value =22.2 x1 =1, x 2 =0, x 3 =0.6, x 4 =1 Objective value =22 x1 =1, x 2 =0.5, x 3 =0, x 4 =1 Objective value =22 x1 =1, x 2 =0, x 3 =1 , x 4 =0.5 x3 =0 x3 =1 Objective value =22.2 x1 =1, x 2 =0, x 3 =0.6, x 4 =1 Objective value =22 x1 =1, x 2 =0.5, x 3 =0, x 4 =1 Objective value =22 x1 =1, x 2 =0, x 3 =1, x 4 =0.5 Objective value =21.66 x1 =1, x 2 =0.33, x 3 =1, x 4=0 Objective value =22 x1 =0.75, x 2 =0, x 3 =1, x 4 =1 x3 =0 x3 =1 x4 =1x4 =0 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 P rofit=22.2 3.2.1 Branch and bound tree Slide 13 3.3 Pigeonhole Problem Slide 14 Slide 15 • There are n + 1 pigeons with n holes. We want to place the pigeons in the Slide 16 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. Slide 17 • Formulation 1: xij = 1, i = 1, . . . , n + 1 j xij + xkj ≤ 1, ∀j, i � k= 4� Objective value =21 x1 =0 , x 2 =1 , x 3 =1 , x 4 =1 Infeasible x1 =1x1 =0 Objective value =22.2 x1 =1, x 2 =0, x 3 =0.6, x 4 =1 Objective value =22 x1 =1, x 2 =0.5, x 3 =0, x 4 =1 Objective value =22 x1 =1, x 2 =0, x 3 =1, x 4 =0.5 Objective value =21.66 x1 =1, x 2 =0.33, x 3 =1, x 4=0 Objective value =22 x1 =0.75, x 2 =0, x 3 =1, x 4 =1 x3 =0 x3 =1 x4 =1x4 =0 • Formulation 2: xij = 1, i = 1, . . . , n + 1 j � n+1 xij ≤ 1, ∀ji=1 Which formulation is better for the problem? Slide 18 • The pigeonhole problem is infeasible. • For Formulation 1, feasible solution xij = n 1 for all i, j. O(n3) constraints. Nearly c omplete enumeration is needed for LP-based BB, since the prob- lem remains fea sible after fixing many variables. • Formulation 2 Infeasible. O(n) constraints. • Mesage: For mulation of the problem is important! 3.4 Preprocessing Slide 19 • An effective way of improving integer programming formulations prior to and during branch-and-bound. • Logical Tests – Removal of emp ty (all zeros) rows and columns; – Removal of rows dominated by multiples of other rows; – strength ening the bounds within rows by comparing individual variables and coefficients 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 conn ection between variables. For …