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(x20,X E 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; If relaxed solution is worse than incumbent. Then delete D If no feasible solution. Then delete D II. Otherwise Branch to smaller subproblems 1) Partition D into subproblems D,. D 2) Apply b&b to all subproblemsSolving 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 Di • If relaxed solution is worse than incumbent, Then delete Di . • If no feasible solution, Then delete Di . II. Otherwise Branch to smaller subproblems 1) Partition D into subproblems D1 … Dn 2) Apply B&B to all subproblems