Example: B&b for bIPs Solve Maxz=9X1+5x2+6X3+4x4 Subject to 6x1+3x2+5x3+2x4≤10 X3+x4≤ <0 +x4≤0 x1≤1,x1≥0, Dequeue Queue Incumbent: none Best cost zx.-inf Example: b&b for bIPs Maxz=9X1+5x2+6x3+4 Subject 6x1+3x2+5x3+2x4≤10 x3+x4≤1 <0 ≤0 ≤0, integer Z=16,,x=<0.83331,0,1> Queue: Bound & Constrain x, by 3 Ir bent. Relax to Lp Best cost zx.-inf SolveExample: 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 • Dequeue {} {} 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 • Bound {} • Constrain xi by {} • Relax to LP • Solve Z = 16.5, x = <0.8333,1,0,1> {}