Example: b&b for bIPs Solve Max Z=9x,+5x, +6x,+4x Subject to 6x1+3x,+5x3+2x4≤10 x4≤ <0 x2+x4≤0 z=16.5,X=<0.8333,1,0,1> Try to fathom: infeasible? Incumbent: none worse than incumbent? Best cost zx.-inf integer solution? Example: b&b for bIPs Maxz=9X1+5x2+6x3+4 Subject to 6x1+3x2+5x3+2x4≤10 X4≤ 1+x3≤0 ≤0 ≤0, integer z=16.5,X=<0.8333,1,0,1> Branch Queue:{x1=0}{x1=1} select unassigned Ir bent not ck Best cost zx.-inf Split on xiExample: B&B for BIPs Solve: Max Z = 9x1 + 5x2 + 6x3 + 4x4 Subject to: – 6x1 + 3x2 + 5x3 + 2x4 10 – x3 + x4 1 – -x1 + x3 0 – -x2 + x4 0 – xi 1, xi • 0, xi 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 = 9x1 + 5x2 + 6x3 + 4x4 Subject to: – 6x1 + 3x2 + 5x3 + 2x4 10 – x3 + x4 1 – -x1 + x3 0 – -x2 + x4 0 – xi 1, xi • 0, xi integer Queue: Incumbent: none Best cost Z*: - inf • Branch: • select unassigned xi • pick non-integer • Split on xi Z = 16.5, x = <0.8333,1,0,1> {x1 = 0}{x1 = 1} {} {x1 = 0} {x1 = 1}