Integer Programming and Branch and Bound Sommer Gentry November 24 th , 2003 Adapted from slides by Eric Feron and Brian Williams, 16.410, 2002. Integer Programming (IP) ? What is it? ? Expressing decisions with IP – Exclusion between choices – Exclusion between constraints ? Solutions through branch and bound – Characteristics – Solving Binary IPs – Solving Mixed IPs and LPs Courtesy of Sommer Gentry. Used with permission. Integer Programs LP: Maximize 3x 1 + 4x 2 Subject to: x 1 ? 4 2x 2 ? 12 3x 1 + 2x 2 ? 18 x 1 , x 2 ? 0 IP: Maximize 3x 1 + 4x 2 Subject to: x 1 ? 4 2x 2 ? 12 3x 1 + 2x 2 ? 18 x 1 , x 2 ? 0 x 1 , x 2 integers a) b) c) d) e) x 1 x 2 Integer programs are LPs where some variables are integers Why Integer programming? 1. Some variables are not real-valued: ? Boeing only sells complete planes, not fractions. 2. Fractional LP solutions poorly approximate integer solutions: ? For Boeing Aircraft Co., producing 4 versus 4.5 airplanes results in radically different profits. Often a mix is desired of integer and non-integer variables (MILP). Integer Programming Graphical representation of IP Integer Programming (IP) ? What is it? ? Making decisions with IP – Exclusion between choices – Exclusion between constraints ? Solutions through branch and bound – Characteristics – Solving Binary IPs – Solving Mixed IPs and LPs “Yes or no” decisions encoded with binary variables: 1 if decision is yes x j 0 if decision is no. Binary Integer Programming (BIP): ? Binary variables + linear constraints. Integer Programming for Decision Making Problem: 1. Cal wants to expand: ? Build new factory in Los Angeles, San Francisco, or both. ? Build new warehouse (only one). ? Warehouse must be built close to city of a new factory. 2. Available capital: $10,000,000 3. Cal wants to maximize “total net present value” (profitability vs. time value of money) NPV Price 1 Build a factory in L.A.? $9m $6m 2 Build a factory in S.F.? $5m $3m 3 Build a warehouse in L.A.? $6m $5m 4 Build a warehouse in S.F.? $4m $2m Binary Integer Programming Example: Cal Aircraft Manufacturing Company What decisions are to be made? 1. Build factory in LA 2. Build factory in SFO 3. Build warehouse in LA 4. Build warehouse in SFO 1 if decision i is yes Introduce 4 binary variables x i = 0 if decision i is no Binary Integer Programming Example: Cal Aircraft Manufacturing Company 1. Cal wants to expand (TBD) 2. Available capital: $10,000,000 3. Cal wants to maximize “total net present value” (profitability vs. time value of money) NPV Price 1 Build a factory in L.A.? $9m $6m 2 Build a factory in S.F.? $5m $3m 3 Build a warehouse in L.A.? $6m $5m 4 Build a warehouse in S.F.? $4m $2m What is the objective? ? Maximize NPV: Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Remaining constraints? ? Don’t go beyond means: 6x 1 + 3x 2 + 5x 3 + 2x 4 <10 Binary Integer Programming Example: Cal Aircraft Manufacturing Company LA factory(x 1 ), SFO factory(x 2 ), LA warehouse(x 3 ),SFO warehouse (x 4 ) ? Build new factory in Los Angeles, San Francisco, or both. ? Build new warehouse (only one). ? Warehouse must be built close to city of a new factory. What are the constraints between decisions? 1. Only one warehouse: x 3 exclusive-or x 3 x 3 + x 4 < 1 2. Warehouse in LA only if Factory is in LA: x 3 implies x 1 x 3 –x 1 < 0 3. Warehouse in SFO only if Factory is in SFO: x 4 implies x 2 x 4 -x 2 < 0 Binary Integer Programming Example: Cal Aircraft Manufacturing Company ? Mutually exclusive choices ? Example: at most 2 decisions in a group can be yes: LP Encoding: x 1 +…+ x k < 2. Encoding Choices: An Example LA factory(x1), SFO factory(x2), LA warehouse(x3),SFO warehouse (x4) ? Build new factory in Los Angeles, San Francisco, or both. ? Build new warehouse (only one). ? Warehouse must be built close to city of a new factory. What are the constraints between decisions? 1. Only one warehouse: x 3 exclusive-or x 4 x 3 + x 4 < 1 2. Warehouse in LA only if Factory is in LA: x 3 implies x 1 x 3 –x 1 < 0 3. Warehouse in SFO only if Factory is in SFO: x 4 implies x 2 x 4 - x 2 < 0 Binary Integer Programming Example: Cal Aircraft Manufacturing Company Complete binary integer program: Maximize Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: 6x 1 + 3x 2 + 5x 3 + 2x 4 <10 x 3 + x 4 < 1 x 3 -x 1 < 0 x 4 -x 2 < 0 x j < 1 x j = {0,1}, j=1,2,3,4 x j > 0 Binary Integer Programming Example: Cal Aircraft Manufacturing Company Integer Programming (IP) ? What is it? ? Making decisions with IP – Exclusion between choices – Exclusion between constraints ? Solutions through branch and bound – Characteristics – Solving Binary IPs – Solving Mixed IPs and LPs Cooperative Path Planning MILP Encoding: Constraints ? Min J T Receding Horizon Fuel Cost Fn ?s ij ? w ij , etc. State Space Constraints ? s i +1 = As i + Bu i State Evolution Equation ? x i ? x min + My i1 -x i ? -x max + My i2 y i ? y min + My i3 Obstacle Avoidance -y i ? -y max + My i4 6 y ik ? 3 ? Similar constraints for Collision Avoidance (for all pairs of vehicles) Obstacles How do we encode? ? Each obstacle-vehicle pair represents a disjunctive constraint: ? Each disjunct is an inequality – if xR, yR are co-ordinates of red vehicle, inequalities above might be: –xR< 3 – yR > 4, etc. ? Constraints are not limited to rectangular obstacles or obstacles oriented a particular way – (inequalities might include both co-ordinates) Red Vehicle is above obstacle OR Red Vehicle is below obstacle OR Red Vehicle is left of obstacle OR Red Vehicle is right of obstacle ? Mutually exclusive constraints ? Example: Either [ 3x 1 + 2x 2 < 18 (x 1 ,x 2 real) ] Or [ x + 4x < 16]. ? LP Encoding: ? Use Big M to turn-off constraint: Either: 3x 1 + 2x 2 < 18 and x 1 + 4x 2 < 16 + M (and M is very BIG) Or: 3x 1 + 2x 2 < 18 + M and x 1 + 6x 2 < 16 Encoding Exclusion Constraints ? Use binary y to decide which constraint to turn off: 3x1 + 2x2 < 18 + y M x1 + 2x2 < 16 + (1-y)M y ? {0,1} Cooperative Path Planning MILP Encoding: Constraints ? Min J T Receding Horizon Fuel Cost Fn ?s ij ? w ij , etc. State Space Constraints ? s i +1 = As i + Bu i State Evolution Equation ?x i ? x min + My i1 -x i ? -x max + My i2 y i ? y min + My i3 Obstacle Avoidance -y i ? -y max + My i4 6 y ik ? 3 At least one enabled ? Similar constraints for Collision Avoidance (for all pairs of vehicles) ? K out of N constraints hold: f 1 (x 1 , x 2 ,…x n ) < d 1 OR : f N (x 1 , x 2 , …, x n ) < d N where f i are linear expressions ? LP Encoding: ? Introduce y i to deselect each constraint: ? Constrain K of y i to select constraints: ? Use Big M to turn-off constraint: f1(x 1 , ---, x n ) < d 1 + My 1 : f N (x 1 , ---, x n ) < d N + My N Encoding Exclusion Constraints | d N i i KNy 1 ? At most K of N hold: |  N i i KNy 1 ? Function has one out of n possible values: a 1 x 1 + . . . a n x n = [d 1 or d 2 …or d p ] ? LP Encoding: y i ? {0,1} i=1,2,…p ( 6 y i ) =1 a 1 x 1 + . . . a n x n = (6 L d i y i ) Encoding Finite Domain Functions ? Fixed – charge problem: f i (x j ) = | k j + c j x j if x j >0 | 0 if x j =0 Minimizing costs: Minimizing z=f 1 (x 1 ) +---+ f n (x n ) Yes or no decisions: should each of the activities be undertaken? Encoding Constraints Introduce auxiliary variables: y 1 , …, y n = 0,1 y = 1 if x > 0 0 if x = 0 Which can be written as a linear constraint using big M: x <yM |  n i iiii ykxcZ 1 Integer Programming (IP) ? What is it? ? Making decisions with IP – Exclusion between choices – Exclusion between constraints ? Solutions through Branch and Bound – IP Characteristics – Solving Binary IPs – Solving Mixed IPs and LPs Na?ve approach: rounding ? A simple way to solve an IP might be to round the non-integer solution to the nearest feasible integer. In practice, try it! ? In theory, this idea makes no sense at all. Consider ? Optimal solution x* is (13/7,0) integer,,0,0 1347Subject to 1121Maximize 2121 21 21 xxxx xx xxZ tt d  Na?ve approach: rounding ? The rounded solution is x*=(2,0). But this is not even feasible! ? By enumeration, feasible x are (0,0) (0,1) (0,2) (0,3) (1,1) (1,0) ? The optimal integer solution x* is (0,3) [value = 33] which is nowhere near (13/7,0). ? In general, just finding a nearby feasible point is computationally challenging Solving Integer Programs: Characteristics ? Fewer feasible solutions than LPs. ? Worst-case exponential in # of variables. ? Commercial software: –Cplex Solving Integer Programs ? Branch and Bound – Binary Integer Programs – Integer Programs – Mixed Integer (Real) Programs ? Cutting Planes Branch and Bound Problem: Optimize f(x) subject to A(x) ? 0, x ? D B & B - an instance of Divide & Conquer: I. Bound D’s solution and compare to alternatives. 1) Bound solution to D quickly. ? Perform quick check by relaxing hard part of problem. ? Relax integer constraints. Relaxation is LP. 2) Use bound to “fathom” D if possible. ? If relaxed solution is integer, Then keep soln if best found to date (“incumbent”), delete D i ? If relaxed solution is worse than incumbent, Then delete D i . ? If no feasible solution, Then delete D i . II. Otherwise Branch to smaller subproblems 1) Partition D into subproblems D 1 … D n 2) Apply B&B to all subproblems. B&B for Binary Integer Programs (BIPs) Problem: Optimize f(x) st A(x) ? 0, x i ?{0,1}, x?D Domain D i encoding: ? partial assignment to x, – {x1 = 1, x2 = 0, …} Branch Step: 1. Find variable x j that is unassigned in D i 2. Create two subproblems by splitting D i : ?D i1 { D i ? {x j = 1} ?D i0 { D i ?{x j = 0} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-x 1 + x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: {} Incumbent: none Best cost Z*: - inf ? Initialize {} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-x 1 + x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: {} Incumbent: none Best cost Z*: - inf ? Dequeue {} {} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-x 1 + x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: none Best cost Z*: - inf ? Bound {} ? Constrain x i by {} ? Relax to LP ? Solve Z = 16.5, x = <0.8333,1,0,1> {} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-x 1 + x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: none Best cost Z*: - inf ? Try to fathom: ? infeasible? ? worse than incumbent? ? integer solution? Z = 16.5, x = <0.8333,1,0,1> {} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-x 1 + x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: none Best cost Z*: - inf ?Branch: ? select unassigned x i ? pick non-integer ? Split on x i Z = 16.5, x = <0.8333,1,0,1> {x 1 = 0}{x 1 = 1} {} {x 1 = 0} {x 1 = 1} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-x 1 + x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: none Best cost Z*: - inf ? dequeue: ? depth first or ?best first Z = 16.5, x = <0.8333,1,0,1> {x 1 = 0}{x 1 = 1} {} {x 1 = 0} {x 1 = 1} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-x 1 + x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: none Best cost Z*: - inf ? Bound {x 1 = 0} ? constrain x by {x 1 = 0} ? relax to LP ? solve {x 1 = 1} {} {x 1 = 0} {x 1 = 1} Z = 16.5, x = <0.8333,1,0,1> Example: B&B for BIPs Solve: Max Z = 9 0 + 5x 2 + 6x 3 + 4x 4 Subject to: –6 0 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-0 + x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: none Best cost Z*: - inf ? Bound {x 1 = 0} ? constrain x by {x 1 = 0} ? relax to LP ? solve {x 1 = 1} {} {x 1 = 0} {x 1 = 1} Z = 16.5, x = <0.8333,1,0,1> Example: B&B for BIPs Solve: Max Z = 9 0 + 5x 2 + 6x 3 + 4x 4 Subject to: –6 0 +3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-0+ x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: none Best cost Z*: - inf ? Bound {x 1 = 0} ? constrain x by {x 1 = 0} ? relax to LP ? solve {x 1 = 1} {} {x 1 = 0} {x 1 = 1} Z = 19,5, x = <0,1,0,1> Example: B&B for BIPs Solve: Max Z = 9 0 + 5x 2 + 6x 3 + 4x 4 Subject to: –6 0 +3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-0+ x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: none Best cost Z*: - inf {x 1 = 1} {} {x 1 = 0} {x 1 = 1} Z = 19,5, x = <0,1,0,1> ? Try to fathom: ? infeasible? ? worse than incumbent? ? integer solution? Example: B&B for BIPs Solve: Max Z = 9 0 + 5x 2 + 6x 3 + 4x 4 Subject to: –6 0 +3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-0+ x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {x 1 = 1} {} {x 1 = 0} {x 1 = 1} Z = 19,5, x = <0,1,0,1> ? Try to fathom: ? infeasible? ? worse than incumbent? ? integer solution? Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-x 1 + x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {x 1 = 1} {} {x 1 = 0} {x 1 = 1} Z = 19,5, x = <0,1,0,1> ? Dequeue and bound Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-1 1 + x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {} {x 1 = 0} {x 1 = 1} Z = 16,2, x = <1,.8,0,.8> ? Dequeue and bound Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-1 1 + x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {x 1 = 1} {} {x 1 = 0} {x 1 = 1} Z = 16.2, x = <1,.8,0,.8> ? Try to fathom: ? infeasible? ? worse than incumbent? ? integer solution? Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-1 1 + x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {x 2 = 1}{x 2 = 0} {} {x 1 = 0} {x 1 = 1} Z = 16.2, x = <1,.8,0,.8> ?Branch ? Dequeue {x 2 = 1} {x 2 = 0} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-1 1 + x 3 ? 0 –-x 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {x 2 = 0} {} {x 1 = 0} {x 1 = 1} Z = 16.2, x = <1,.8,0,.8> ? Bound {x 2 = 1} {x 2 = 0} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-1 1 + x 3 ? 0 –-1 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {x 2 = 0} {} {x 1 = 0} {x 1 = 1} Z = 16, x = <1,1,0,.5> ? Bound {x 2 = 1} {x 2 = 0} Try to fathom: ? infeasible? ? worse than incumbent? ? integer solution? Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-1 1 + x 3 ? 0 –-1 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {x 2 = 0} {} {x 1 = 0} {x 1 = 1} Z = 16, x = <1,1,0,.5> ?Branch {x 2 = 1} {x 2 = 0} {x 3 = 1} {x 3 = 0} 3 = 1} {x 3 = 0}{x 2 = 0} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-1 1 + x 3 ? 0 –-1 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {} {x 1 = 0} {x 1 = 1} Z = 16, x = <1,1,0,.5> ? Bound {x 2 = 1} {x 2 = 0} {x 3 = 1} {x 3 = 0} {x 3 = 1} {x 3 = 0}{x 2 = 0} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-1 1 + x 3 ? 0 –-1 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {} {x 1 = 0} {x 1 = 1} Z = 16, x = <1,1,0,.5> ? Bound {x 2 = 1} {x 2 = 0} {x 3 = 1} {x 3 = 0} {x 3 = 0}{x 2 = 0} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –1 3 + x 4 ? 1 –-1 1 + 1 3 ? 0 –-1 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {} {x 1 = 0} {x 1 = 1} ? Bound {x 2 = 1} {x 2 = 0} {x 3 = 1} {x 3 = 0} {x 3 = 0}{x 2 = 0} Try to fathom: ? infeasible? Z = 16, x = <1,1,0,.5> Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-1 1 + x 3 ? 0 –-1 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {} {x 1 = 0} {x 1 = 1} {x 2 = 1} {x 2 = 0} {x 3 = 1} {x 3 = 0} {x 2 = 0} ? Dequeue & bound Z = 16, x = <1,1,0,.5> Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-1 1 + x 3 ? 0 –-1 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {} {x 1 = 0} {x 1 = 1} {x 2 = 1} {x 2 = 0} {x 3 = 1} {x 3 = 0} {x 2 = 0} ? dequeue & bound Z = 16, x = <1,1,0,.5> Try to fathom: ? infeasible? ? worse than incumbent? ? integer solution? Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-1 1 + x 3 ? 0 –-1 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {} {x 1 = 0} {x 1 = 1} {x 2 = 1} {x 2 = 0} {x 3 = 1} {x 3 = 0} {x 4 = 0} {x 4 = 1}{x 2 = 0} ? dequeue & bound Z = 14, x = <1,1,0,0> Try to fathom: ? infeasible? ? worse than incumbent? ? integer solution? {x 4 = 0} {x 4 = 1} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-1 1 + x 3 ? 0 –-1 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {} {x 1 = 0} {x 1 = 1} {x 2 = 1} {x 2 = 0} {x 3 = 1} {x 3 = 0} ? dequeue & bound Z = 14, x = <1,1,0,0> Try to fathom: ? infeasible? ? worse than incumbent? ? integer solution? {x 4 = 0} {x 4 = 1} x = <1,1,0,0> 14 {x 4 = 1}{x 2 = 0} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 +4x 4 Subject to: –6x 1 + 3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + 1 4 ? 1 –-1 1 + x 3 ? 0 –-1 2 + 1 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {} {x 1 = 0} {x 1 = 1} {x 2 = 1} {x 2 = 0} {x 3 = 1} {x 3 = 0} ? dequeue & bound Z = 18, x = <1,1,0,1> Try to fathom: ? infeasible? ? worse than incumbent? ? integer solution? {x 4 = 0} {x 4 = 1} x = <1,1,0,0> 14 {x 4 = 1}{x 2 = 0} Example: B&B for BIPs Solve: Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4 Subject to: –6x 1 +3x 2 + 5x 3 + 2x 4 ? 10 –x 3 + x 4 ? 1 –-1 1 + x 3 ? 0 –-1 2 + x 4 ? 0 –x i ? 1, x i ? 0, x i integer Queue: Incumbent: x = <0,1,0,1> Best cost Z*: 9 {} {x 1 = 0} {x 1 = 1} {x 2 = 1} {x 2 = 0} {x 3 = 1} {x 3 = 0} ? dequeue & bound Z = 13.8, x = <1,0,.8,0> Try to fathom: ? infeasible? ? worse than incumbent? ? integer solution? {x 4 = 0} {x 4 = 1} x = <1,1,0,0> 14 {x 2 = 0} Integer Programming (IP) ? What is it? ? Making decisions with IP – Exclusion between choices – Exclusion between constraints ? Solutions through branch and bound – Characteristics – Solving Binary IPs – Solving Mixed IPs and LPs Example: B&B for MIPs Max Z = 4x 1 -2x 2 + 7x 3 -x 4 Subject to: –x 1 + 5x 3 ? 10 –x 1 + x 2 -x 3 ? 1 –6x 1 + 5x 2 ? 0 –-x 1 + 2x 3 –2x 4 ? 3 –x i ? 0, x i integer x 1 , x 2 , x 3 , {} {x 1 ? 1} {x 1 ? 2} {x 2 ? 1} {x 2 ? 2} {x 1 = 0} {x 1 = 1} Incumbent: Best cost Z*: Z = 14.25, x = <1.25,1.5,1.75,0> Z = 14.2, x = <1,1.2,1.8,0> Infeasible, x = < ?2,?,?,?> Infeasible, x = <1,?1,?,?> x = <0,0,2,.5> 13.5 Z = 14 1/6, x = <5/6,1,11/6,0> Z = 12 1/6, x = <5/6,2,11/6,0> Z = 13.5, x = <0,0,2,.5> Cutting planes methods ? Cutting planes are an alternative to Branch and Bound search, though the methods do have similarities ? Gomory invented the first finitely terminating cutting plane method in 1958. Cutting planes cut off non-integer solutions Cutting planes algorithm ? Solve the linear programming relaxation of the integer program. ? If x*, the optimal solution, is integer, then x* is optimal for the integer program. ? If not, add a linear inequality constraint (cutting plane) that all integer solutions to the original problem satisfy but that is violated by x*. Repeat all steps. Gomory cutting planes ? Given a problem with all variables integer constrained, solve the relaxed LP and examine the final simplex tableau. Take one equality with a fractional right-hand- side b i . This is an equality that forces an integer constrained variable to be fractional. ikikjiji bxaxax  Non-basic variables and coefficients Gomory cutting planes ? Since at this tableau all of x j through x k are 0, and in all feasible solutions they are >0, it must be that ? So add the cutting plane constraint that x* does not satisfy but all integer solns do: ? ? ?? ?? ?? ?? ikikjiji ikikjijikikjiji bxaxax bxaxaxxaxax d d   Example: Gomory cutting plane integer,,0,0 4 964Subject to 2Minimize 2121 21 21 21 xxxx xx xx xxZ tt d d  integer,,, ,0,0,0,0 4 964Subject to 2Minimize 4321 4321 421 321 21 xxxx xxxx xxx xxx xxZ tttt    Example: Gomory continued ? Solve the LP relaxation to find x*=(3/2,5/2) ? One of the equations in the final simplex tableau is: ? Taking the floor of all non-basic variable coefficients and the right-hand-side, get and add this constraint to the LP 2/5 10 1 10 1 432 d xxx 2 2 dx Example: Gomory continued ?Solve ? And find x*=(3/4,2). One of the equations in the optimal tableau is 0,0,0,0 2 4 964Subject to 2Minimize 4321 52 421 321 21 tttt     xxxx xx xxx xxx xxZ 4 3 2 3 4 1 531 d xxx Example: Gomory continued ? Add the new Gomory cut: ? Notice that in terms of the original variables, the new cut is: ? Add this constraint and solve the relaxed LP 0 531 d xxx 753 21 d xx 0,0,0,0,0 753 2 4 964Subject to 2Minimize 54321 21 52 421 321 21 ttttt      xxxxx xx xx xxx xxx xxZ Example: Gomory continued ? The new x*=(1,2), which is integer. Why is this x* definitely the optimal solution to the original integer program? – x*=(1,2) is integer so it is feasible for the integer program – No better integer-valued x existed at the start, because none of the Gomory cuts can eliminate any integer solution, regardless of its value. Problems with cutting planes ? Each cutting plane usually eliminates a very small part of the feasible region. ? Although finite, no cutting plane method is polynomial-time. ? The more one knows about the specific structure of the problem, the better one can do with cutting planes. Specialized cutting plane algorithms sometimes work remarkably well, and CPLEX allows you to turn specific types on and off.