Example: b&b for bIPs Solve XI Max z 5X,+6X2+4 6x1+3x,+5x3+2x4≤10 x4≤ <0 x2+x4≤0 Z Queue:{x∠0}{x1=1} depth first or Incumbent: none best first Best cost zx.-inf Example: b&b for bIPs Maxz=9X1+5x2+6x3+4 Subject 6x1+3x2+5x3+2x4≤10 X4≤ <0 ≤0 Z Queue: x=13 Bound (x1=0 constrain x by (x1=03 Ir bent not Best cost zx.-infExample: 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: • depth first or • best first Z = 16.5, x = <0.8333,1,0,1> {x1 = 0}{x1 = 1} {} {x1 = 0} {x1 = 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 • Bound {x1 = 0} • constrain x by {x1 = 0} • relax to LP • solve {x1 = 1} {} {x1 = 0} {x1 = 1} Z = 16.5, x = <0.8333,1,0,1>