15.083 Lecture 19: Enumerative Methods

15.083J Integer Programming and Combinatorial Optimization Enumerative Methods A knapsack problem • Let’s focus on maximization integer linear programs with only binary variables • For example: a knapsack problem with 6 items max 16x1 + 22x2 + 12x3 + 8x4 + 11x5 + 19x6 s.t. 5x1 + 7x2 + 4x3 + 3x4 + 4x5 + 6x6 ≤ 14 x1 , x2 , . . . , x6 ∈ {0, 1} Complete enumeration • Complete enumeration systematically considers all possible solutions – n binary variables x1 , . . . , xn ⇒ 2n possible solutions • After considering all possible solutions, choose best feasible solution • Usual idea: iteratively break the problem into 2 – For example, first, we consider consider separately the cases that x1 = 0 and x1 = 1 An enumeration tree • Let’s enumerate all possible solutions of our illustrative knapsack problem • 6 binary decision variables x1 , . . . , x6 • We can enumerate all possible solutions systematically using a tree • Start with root node – No variables have been fixed in value 0 • Branch the possibilities for x1 : x1 = 0 or x1 = 1 1 0 x1 = 0 x1 = 1 1 2 • Next, branch the possibilities for x2 : x2 = 0 or x2 = 1 0 x1 = 0 x1 = 1 1 2 x2 = 0 x2 = 1 3 x2 = 0 4 x2 = 1 5 6 • Keep building the tree, branching the possibilities for x3 , x4 , x5 , x6 0 x1 = 0 x2 = 0 1 x1 = 1 x2 = 1 3 x2 = 0 4 2 x2 = 1 5 6 • Each node corresponds to a partial solution – For example, node 4 ⇔ fix x1 = 0 and x2 = 1 – partial solution of node 4 = x(4) = (0, 1, #, #, #, #) • Each of the 64 leaves of the tree (nodes at the bottom) corresponds to a solution: a complete assignment of variables Subtrees of an enumeration tree x1 = 0 x2 = 0 3 1 0 x1 = 1 x2 = 1 x2 = 0 4 5 2 x2 = 1 6 • Subtree (or descendants) of node i = nodes obtained from node i from subsequent branch­ ing 2 • Example: red nodes = subtree of node 4 • Recall: node 4 ⇔ partial solution x(4) = (0, 1, #, #, #, #) • Leaves of subtree of node 4 ⇔ completions of x(4) – (full) solutions that have the same fixed variables as x(4) • Idea: stop branching from a node as soon as possible – Suppose we look at node 4 and conclude none of its descendants can be optimal ⇒ Can eliminate 1/4 the solutions at once! Incumbent solutions • Goal of branch and bound: find an optimal (or at least a good feasible) solution to some optimization model • The incumbent solution at any stage of branch and bound is the best feasible solution known so far (in terms of objective value) • Notation: – Incumbent solution x̂ – Incumbent solution’s objective function value v̂ • Most branch and bound algorithms have subroutines that run at the beginning trying to get a good feasible solution Eliminating nodes and subtrees • Let’s look at our knapsack problem • Suppose that we have an incumbent solution x̂ with objective value v̂: x̂ = (1, 1, 0, 0, 0, 0) v̂ = 38 • Let’s look at the subtree of node 4 in our enumeration tree 0 1 3 2 4 5 3 6 0 x1 = 0 1 x2 = 1 4 • Node 4 ⇔ partial solution x(4) = (0, 1, #, #, #, #) • All possible completions of x(4) ⇔ Leaves of node 4’s subtree • Candidate problem for node 4: find the best possible completion of x(4) v (4) = max s.t. 16x1 + 22x2 + 12x3 + 8x4 + 11x5 + 19x6 5x1 + 7x2 + 4x3 + 3x4 + 4x5 + 6x6 ≤ 14 x1 = 0, x2 = 1 x1 , x2 , . . . , x6 ∈ {0, 1} • LP relaxation gives us upper bound on v (4) : ṽ (4) = max s.t. 16x1 + 22x2 + 12x3 + 8x4 + 11x5 + 19x6 5x1 + 7x2 + 4x3 + 3x4 + 4x5 + 6x6 ≤ 14 x1 = 0, x2 = 1 0 ≤ xi ≤ 1, i = 1, . . . , 6 • Solve LP relaxation: ṽ (4) = 44 • Best completion of x(4) has value v (4) ≤ ṽ (4) = 44 • Incumbent solution has value v̂ = 38 ⇒ It is possible that some completion of x(4) has a better solution value than 38 ⇒ Need to examine solutions that branch from node 4 • What if we had an incumbent solution with value v̂ = 45? • Then no completion of x(4) is better than our incumbent, since v (4) ≤ ṽ (4) = 44 < 45 = v̂ • We can terminate or fathom node 4: we do not need to branch the subtree of node 4 4 Branch and bound in a nutshell • Branch and bound creates the enumeration tree – one node at a time – one branch at a time • Before branching on a node j, it solves the LP relaxation of the node j’s candidate problem – Candidate problem ∗ original problem with variables fixed according to the partial solution x(j) corre­ sponding to node j ∗ finds best completion of partial solution x(j) • Depending on the solution to the candidate problem, it either – terminates node j – branches on node j • We will examine 4 cases Termination by infeasibility 0 1 3 4 infeasible • Node j ⇔ partial solution x(j) • Feasible region of candidate problem of node j ⇔ All possible completions of x(j) ⇔ All leaves of node j’s subtree • Case 1: Termination by infeasibility. The LP relaxation of the candidate problem of node j is infeasible ⇒ The candidate problem of node j is infeasible ⇒ Any completion of the partial solution x(j) is infeasible for the original problem! ⇒ Terminate node j (do not branch from node j) 5 Termination by bound 0 1 3 4 by bound • Notation: v̂ = value of incumbent solution v (j) = optimal value of candidate problem for j ṽ (j) = optimal value of LP relaxation of candidate problem for j • Recall: candidate problem of j finds best completion of partial solution x(j) • Case 2: Termination by bound. ṽ (j) ≤ v̂ ⇒ v (j) ≤ ṽ (j) ≤ v̂ ⇒ No completion of x(j) is better than the incumbent ⇒ Terminate node j (do not branch from node j) Termination by solving 0 1 3 4 by solving • Case 3: Termination by solving. ṽ (j) > v̂ and the optimal solution x̃(j) of the LP relaxation of node j’s candidate problem is integer • x̃(j) is integer ⇒ x̃(j) is optimal for the candidate problem ⇒ v (j) = ṽ (j) > v̂ ⇒ We have found a feasible solution that is better than the incumbent ⇒ Save solution x(j) as new incumbent 6 ⇒ No completion of partial solution x(j) will be better ⇒ Terminate node j (do not branch from node j) Branching 0 1 3 4 x3 = 0 x3 = 1 • Case 4: Branching. ṽ (j) > v̂ and the optimal solution x̃(j) of the LP relaxation of node j’s candidate problem is not integer ⇒ It is possible that a completion of the partial solution x(j) may have a better objective value • Branch at node j: pick some variable that is not fixed in the partial solution x(j) and create a child node for each possible value Active nodes • A node is called active if it has been analyzed: – it has no children – it has not been terminated • For example: 0 1 2 3 4 by solving The active nodes here are 2 and 3 • Initially, the only active node is the root node 0 • Branch and bound stops when there are no more active nodes 7 LP-based branch and bound algorithm for 0-1 ILPS • We have essentially described the whole branch and bound algorithm, piecemeal • We’ll give an abbreviated version of the algorithm • A = set of active nodes • x̂ = incumbent solution, v̂ = value of incumbent solution • LP(t) = LP relaxation of node t’s candidate problem • x̃(t) = optimal solution to LP(t) , ṽ(t) = optimal value of LP(t) 0. Initialize. • A ← {partial solution with no variables fixed} • x̂ ← ∅, v̂ ← −∞ (or some external heuristic finds an incumbent) • Solution counter t ← 0 1. Select. • If A = ∅, then x̂ is optimal if it exists, and the problem is infeasible if no incumbent exists • Else, – remove a node from A – label this node t – categorize t into one of the four cases • Case 1: Termination by infeasibility LP(t) is infeasible. Terminate node t. • Case 2: Termination by bound ṽ (t) ≤ v̂. Terminate node t. • Case 3: Termination by solution ṽ (t) > v̂ and x̃(t) is integer. Terminate node t, set x̂ ← x̃(t) and v̂ ← ṽ (t) • Case 4: Branching ṽ (t) > v̂ and x̃(t) is not integer. Choose a variable that is not fixed in partial solution x(t) and branch on all its possible values • Increment solution counter t ← t + 1, goto Step 1 • Some areas of vagueness: – Which active node to choose in Step 1? ∗ In principle, can select any active node ∗ One potential rule: depth first search - select active node with the most compo­ nents fixed (deepest in tree) – Which variable to branch on? ∗ In principle, can select any variable not fixed at node’s partial solution ∗ One potential rule: choose variable whose LP optimal value at that node is fractional and closest to integer 8 Branch and bound, illustrated v̂ = −∞, x̂ = ∅ 0 x2 = 0 ṽ (0) = 44.4 x2 = 1 • LP relaxation of candidate problem at root node: LP(0) : max s.t. 16x1 + 22x2 + 12x3 + 8x4 + 11x5 + 19x6 5x1 + 7x2 + 4x3 + 3x4 + 4x5 + 6x6 ≤ 14 0 ≤ xi ≤ 1 i = 1, . . . , 6 • Optimal solution: ṽ (0) = 44.4, x̃(0) = (1, 0.43, 0, 0, 0, 1) ⇒ Case 4: branch on x2 v̂ = −∞, x̂ = ∅ 0 x2 = 0 ṽ (1) = 44 ṽ (0) = 44.4 x2 = 1 1 x3 = 0 x3 = 1 • LP relaxation of candidate problem at root node LP(1) : max s.t. 16x1 + 22x2 + 12x3 + 8x4 + 11x5 + 19x6 5x1 + 7x2 + 4x3 + 3x4 + 4x5 + 6x6 ≤ 14 x2 = 0 0 ≤ xi ≤ 1 i = 1, . . . , 6 • Optimal solution: ṽ (1) = 44, x̃(1) = (1, 0, 0.75, 0, 0, 1) ⇒ Case 4: branch on x3 v̂ = −∞, x̂ = ∅ 0 x2 = 0 ṽ (1) = 44 ṽ = 43.25 x5 = 0 x2 = 1 1 x3 = 0 (2) ṽ (0) = 44.4 x3 = 1 2 x5 = 1 • Solve LP(2) : ṽ (2) = 43.25, x̃(2) = (1, 0, 0, 0, 0.75, 1) 9 ⇒ Case 4: branch on x5 v̂ = −∞ 43, x̂ = ∅ x̃(3) ṽ (0) = 44.4 0 x2 = 0 ṽ (1) = 44 x2 = 1 1 x3 = 0 ṽ (2) = 43.25 x3 = 1 2 x5 = 0 ṽ (3) = 43 x5 = 1 3 by solving • Solve LP(3) : ṽ (3) = 43, x̃(3) = (1, 0, 0, 1, 0, 1) • Solving LP(3) yields integer solution that is better than incumbent ⇒ Case 3: replace incumbent with x̃(3) , terminate node 3 v̂ = 43, x̂ = x̃(3) 0 x2 = 0 ṽ (1) = 44 ṽ = 43 x3 = 1 2 x5 = 0 (3) x2 = 1 1 x3 = 0 ṽ (2) = 43.25 ṽ (0) = 44.4 x5 = 1 ṽ (4) = 42.8 3 4 by solving by bound • Solve LP(4) : ṽ (4) = 42.8, x̃(4) = (1, 0, 0, 0, 1, 0.83) ⇒ Case 2: terminate node 4 by bound v̂ = 43, x̂ = x̃(3) 0 ṽ (0) = 44.4 x2 = 0 ṽ (1) = 44 1 x3 = 0 ṽ (2) = 43.25 x5 = 0 ṽ (3) = 43 x2 = 1 x3 = 1 2 5 x5 = 1 ṽ (4) 3 4 by solving by bound x6 = 0 = 42.8 • Solve LP(5) : ṽ (5) = 43.8, x̃(5) = (1, 0, 1, 0, 0, 0.83) 10 ṽ (5) = 43.8 x6 = 1 ⇒ Case 4: branch on x6 v̂ = 43, x̂ = x̃(3) ṽ (0) = 44.4 0 x2 = 0 ṽ (1) = 44 1 x3 = 0 ṽ (2) = 43.25 x3 = 1 2 x5 = 0 ṽ (3) = 43 x2 = 1 x5 = 1 3 ṽ (5) = 43.8 5 4 x6 = 0 x6 = 1 ṽ (4) = 42.8 6 ṽ (6) = 41.6 by bound by bound by solving • Solve LP(6) : ṽ (6) = 41.6, x̃(6) = (1, 0, 1, 0.33, 1, 0) ⇒ Case 2: terminate node 6 by bound v̂ = 43, x̂ = x̃(3) ṽ (0) = 44.4 0 x2 = 0 ṽ (1) = 44 1 x3 = 0 ṽ (2) = 43.25 x3 = 1 2 x5 = 0 ṽ (3) = 43 x2 = 1 x5 = 1 3 ṽ (5) = 43.8 5 4 x6 = 0 x6 = 1 ṽ (4) = 42.8 6 ṽ (6) = 41.6 by bound by bound x1 = 0 by solving ṽ (7) = 43.8 7 x1 = 1 • Solve LP(7) : ṽ (7) = 43.8, x̃(7) = (0.8, 0, 1, 0, 0, 1) ⇒ Case 4: branch on x1 v̂ = 43, x̂ = x̃(3) ṽ (0) = 44.4 0 x2 = 0 ṽ (1) = 44 1 x3 = 0 ṽ (2) = 43.25 x5 = 0 ṽ (3) = 43 3 by solving x2 = 1 x3 = 1 ṽ (5) = 43.8 5 2 x5 = 1 x6 = 1 = 42.8 6 ṽ (6) = 41.6 by bound by bound x1 = 0 4 ṽ x6 = 0 (4) ṽ (8) = 42 7 8 by bound • Solve LP(8) : ṽ (8) = 42, x̃(8) = (0, 0, 1, 0, 1, 1) 11 ṽ (7) = 43.8 x1 = 1 ⇒ Case 2: terminate node 8 by bound v̂ = 43, x̂ = x̃(3) ṽ (0) = 44.4 0 x2 = 0 ṽ (1) = 44 1 x3 = 0 ṽ (2) = 43.25 x3 = 1 2 x5 = 1 3 4 by solving ṽ (5) = 43.8 5 x5 = 0 ṽ (3) = 43 x2 = 1 x6 = 0 x6 = 1 ṽ (4) = 42.8 6 ṽ (6) = 41.6 by bound by bound x1 = 0 ṽ (8) = 42 7 ṽ (7) = 43.8 x1 = 1 8 9 by boundinfeasible • Solve LP(9) : infeasible ⇒ Case 2: terminate node 9 by infeasibility v̂ = 43, x̂ = x̃(3) ṽ (0) = 44.4 0 x2 = 1 x2 = 0 ṽ (1) = 44 1 10 x3 = 0 ṽ (2) = 43.25 x5 = 0 ṽ (3) = 43 3 by solving x3 = 1 2 x6 = 0 5 x5 = 1 4 x6 = 1 ṽ (5) = 43.8 x6 = 0 x6 = 1 ṽ (4) = 42.8 6 ṽ (6) = 41.6 by bound by bound x1 = 0 ṽ (8) = 42 8 7 ṽ (7) = 43.8 x1 = 1 9 by boundinfeasible • Solve LP(10) : ṽ (10) = 44.3, x̃(10) = (1, 1, 0, 0, 0, 0.33) ⇒ Case 4: branch on x6 • And we keep on going in a similar manner until there are no active nodes left 12 v̂ = 43, x̂ = x̃(3) ṽ (0) = 44.4 0 x2 = 1 x2 = 0 1 ṽ (10) = 44.3 10 x6 = 0 x6 = 1 ṽ (11) = 44 ṽ (20) = 44.2 11 20 x3 = 1 x3 = 0 ṽ (12) = 43.5 ṽ 12 x5 = 0 x5 = 1 16 ṽ x4 = 0 ṽ (18) x4 = 1 x1 = 0 14 v ˜ = 44 x1 = 1 x 3 = 0 28 x3 = 1 infeasible ṽ (22) = 43.75 18 19 = 42.3 by boundinfeasible x5 = 0 ṽ (15) = 42.8 = 38 = 43.6 x1 = 1 21 ṽ (16) = 42.6 13 (21) 17 ṽ (13) = 43.3 (14) x1 = 0 (17) 22 27 infeasible x5 = 1 ṽ (23) = 43.66 15 23 by boundby bound x4 = 0 ṽ (24) 26 infeasible x4 = 1 = 41 24 25 by boundinfeasible • We solved 29 LPs to get an optimal solution to the knapsack problem • We found the optimal solution at the third iteration, but could not conclude that this solution was optimal until the 28th iteration • What can we say about the quality of the solution we obtained at the third iteration? Branch and bound family tree terminology • Easiest to explain by a picture: 0 1 3 2 4 • Node 1 is the parent of nodes 3 and 4 • Nodes 1 and 2 are the children of node 0 Parent bounds • Suppose we have a maximization integer linear program • Example: 13 0 1 2 3 4 – x(j) = partial solution at node j – IP(j) = node j’s candidate problem – LP(j) = LP relaxation of node j’s candidate problem – v (j) = optimal value of IP(j) – ṽ (j) = optimal value of LP(j) • v (3) = value of best completion of x(3) • LP(3) = LP(1) + one additional variable fixed ⇒ ṽ (3) ≤ ṽ (1) ⇒ v (3) ≤ v˜(3) ≤ v˜(1) • LP(1) also provides an upper bound on the value of the best completion of x(3) Parent bounds • For maximization ILPs, the optimal value of the LP relaxation of a parent node’s candidate problem provides an upper bound on the objective value of any completion of its children • Similar reasoning for minimization ILPs Terminating nodes with parent bounds • Can use parent bounds to terminate some nodes even faster • Example: ṽ (0) = 80 0 ṽ (1) ṽ (2) = 65 = 75 1 3 2 α β γ by solving • α, β, and γ are active nodes • Suppose new incumbent found at node 3 has value v̂ = 70 • Parent bound: all completions of node 2 have value ≤ 65 ⇒ No point in exploring β, γ, can terminate them immediately 14 • Whenever branch and bound discovers a new incumbent solution, any active node whose parent bound is no better than the value of the new incumbent solution can be immediately terminated How good is the current incumbent? • Sometimes just finding a feasible solution is difficult • Would be nice to approximate how close a given solution is to optimal • LP relaxations and parent bounds can help us do this v̂ = −∞ 43, x̂ = ∅ x̃(3) 0 x2 = 0 ṽ (1) = 44 x5 = 0 ṽ (3) = 43 3 x2 = 1 α 1 x3 = 1 x3 = 0 ṽ (2) = 43.25 ṽ (0) = 44.4 β 2 x5 = 1 γ by solving • At node 3, we get a new incumbent with value v̂ = 43 • Any solution that might improve upon the incumbent is a completion of some active partial solution ⇒ Using parent bounds on α, β, γ, we can conclude at this point in branch and bound that the optimal value must be at most max{44.4, 44, 43.25} = 44.4 • What if we use the current incumbent as an approximation to the optimal solution? • The current incumbent is at most (best possible) − (best known) 44.4 − 43 = = 3.25% best known 43 below optimal • For maximization ILPs, we can obtain an upper bound on the optimal value by – looking at the parent bound of all active nodes, and – taking the highest parent bound • Can use this to obtain a bound in the error in using the incumbent as an approximation 15 Selecting active nodes • We used the depth first search rule in our illustration • Other ideas: – Best first search selects at each iteration an active node with the best parent bound – Depth forward best back search selects ∗ a deepest active node after a branching ∗ an active node with best parent bound after a termination Branch and cut [P] max s.t. 3x1 + 4x2 5x1 + 8x2 ≤ 24 x1 , x2 ≥ 0 x1 , x2 integer [P�� ] max s.t. 3x1 + 4x2 5x1 + 8x2 ≤ 24 x1 + x2 ≤ 4 x1 , x2 ≥ 0 x2 4 3 2 [P�� ] [P] 1 [P� ] 1 2 3 4 5 x1 • Add constraint x1 + x2 ≤ 4 • Note: this constraint holds for all integer feasible solutions, but cuts off feasible solutions from the LP relaxation [P� ] • The constraint x1 + x2 ≤ 4 is a valid inequality for [P] • Branch and cut algorithms modify branch and bound by attempting to strengthen the LP relaxations of the candidate problems by adding valid inequalities • Important: valid inequalities must hold for all feasible solutions to the full model, not just the candidate problems 16 • Added valid inequalities should cut off (render infeasible) the optimal solution to the LP relaxations of the candidate problems • Sophisticated modern ILP codes are typically some variant of branch and cut Branch and bound • It is the starting point for all solution techniques for integer programming. • Lots of research has been carried out over the past 40 years to make it more and more efficient. • But, it is an art form to make it efficient. (We did get a sense why.) • Integer programming is intrinsically difficult. • How to do branching for general integer programs? 17