B&B for Binary Integer Programs(BIPs Problem: Optimize f(x)stA(x)≥0,x1∈{0,1},x∈D Domain D, encoding partial assignment to x, Branch Step 1. Find variable x; that is unassigned in D 2. Create two subproblems by splitting D DO=D,U(x=0) Example: b&b for bIPs Maxz=9X1+5x2+6x3+4 Subject te 6x1+3x2+5x3+2x4≤10 x3+x4≤1 x1+x3≤0 ≤0 x1≤1,x1≥0,x; integ Initialize ueue Incumbent Best cost zx.-infB&B for Binary Integer Programs (BIPs) Problem: Optimize f(x) st A(x) • 0, xi {0,1}, xD Domain Di encoding: • partial assignment to x, – {x1 = 1, x2 = 0, …} Branch Step: 1. Find variable xj that is unassigned in Di 2. Create two subproblems by splitting Di : • Di1 { Di ‰ {xj = 1} • Di0 { Di ‰{xj = 0} 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 • Initialize {}