Chapter 1 left the cargo problem in an unsatisfying state. A plan worth \(19\) was in hand, the relaxation said that nothing could be worth more than \(20\) , and the only way offered to rule out \(20\) was to list all fourteen feasible plans. For fourteen plans that is tolerable. For a knapsack with sixty items it is the thirty-six years computed in Example 1.3.
Branch-and-bound is the method that rules out \(20\) without the list. It splits the problem into pieces, bounds each piece by a relaxation, and discards every piece whose bound shows it cannot contain anything better than the best solution already found. On the cargo problem it examines seven linear programs. It is still an enumeration, and in the worst case it is no better than listing; but the worst case is a matter of how good the bounds are, which is why Chapters 5 and 6 came first.
Throughout this chapter problems are maximizations. For a minimization problem every statement holds with the roles of upper and lower bounds exchanged.
7.1 Divide, bound, and discard
Let \(X\) be the feasible set of an integer program and \(z^\star=\max\{c^{\top}x:x\in X\}\) . Two elementary observations carry the whole method.
Proposition 7.1 (divide). If \(X=X_1\cup X_2\cup\dots\cup X_k\) , then \(z^\star=\max_i z_i^\star\) , where \(z_i^\star=\max\{c^{\top}x:x\in X_i\}\) and the maximum over an empty set is taken to be \(-\infty\) .
Proof. Each \(z_i^\star\le z^\star\) because \(X_i\subseteq X\) . An optimal solution of the whole problem lies in some \(X_i\) , so \(z^\star\le z_i^\star\) for that \(i\) .
The pieces are called subproblems or nodes, because repeated division produces a tree with the original problem at the root. For each node we compute an upper bound \(\bar z_i\ge z_i^\star\) from a relaxation. Alongside, we keep the best feasible solution found so far, the incumbent, with value \(\underline z\) , starting from \(\underline z=-\infty\) .
Proposition 7.2 (three reasons to discard a node). Let \(X_i\) be a node with relaxation bound \(\bar z_i\) , and let \(\underline z\) be the value of the incumbent. The node needs no further division in each of the following cases. (a) Infeasibility: the relaxation of \(X_i\) is infeasible; then \(X_i\) is empty. (b) Bound: \(\bar z_i\le\underline z\) ; then no point of \(X_i\) is better than the incumbent. (c) Integrality: the relaxation’s optimal solution \(\bar x\) is integral; then \(\bar x\) is an optimal solution of the node, and it replaces the incumbent if \(c^{\top}\bar x>\underline z\) .
Proof. (a) \(X_i\) is contained in the feasible region of its relaxation. (b) Every \(x\in X_i\) has \(c^{\top}x\le z_i^\star\le\bar z_i\le\underline z\) . (c) This is Proposition 1.3 applied to the node: an integral optimum of the relaxation is optimal for the integer problem over \(X_i\) , so nothing in \(X_i\) is better than \(\bar x\) .
When \(c\) is an integer vector, every feasible value is an integer and the bound in (b) can be sharpened to \(\lfloor\bar z_i\rfloor\le\underline z\) . A node that is not discarded is divided further. The process is called pruning the tree, and a node discarded for reason (b) is said to be pruned by bound.
7.2 Branching on a fractional variable
With linear programming relaxations there is a natural way to divide. Suppose the relaxation of a node has optimal solution \(\bar x\) and some coordinate \(\bar x_j\) is not an integer. Every integer point satisfies exactly one of
so adding each of these in turn to the node’s constraints splits its integer points between two children and loses none. The fractional point \(\bar x\) satisfies neither, so it is excluded from both children and their relaxations must produce something new. Adding a constraint cannot raise a maximum, so a child’s bound never exceeds its parent’s.
The branch-and-bound algorithm is then: put the root in a list of open nodes. While the list is nonempty, remove a node; solve its relaxation; discard it if Proposition 7.2 applies; otherwise choose a fractional variable and add the two children to the list. When the list is empty, the incumbent is optimal, or, if there is none, the problem is infeasible.
Theorem 7.3 (finiteness and correctness). Suppose the feasible region of the root relaxation is bounded. Then the branch-and-bound algorithm stops after finitely many nodes, and at termination the incumbent is an optimal solution of the integer program, or no incumbent exists and the program is infeasible.
Proof. Because the root relaxation is bounded, there are integers \(\ell_j\le g_j\) with \(\ell_j\le x_j\le g_j\) at every point of it. Attach to each node, for each variable, the integer range obtained from \([\ell_j,g_j]\) by imposing the branching constraints on the path from the root. The relaxation solution \(\bar x\) of a node satisfies those constraints, so \(\bar x_j\) lies between the endpoints of the node’s range for \(x_j\) ; if \(\bar x_j\) is fractional it lies strictly between them, and the two children receive the ranges below \(\lfloor\bar x_j\rfloor\) and above \(\lceil\bar x_j\rceil\) , both nonempty and both strictly shorter. So the total length of the ranges, a nonnegative integer equal to \(D=\sum_j(g_j-\ell_j)\) at the root, decreases by at least one at each level. Hence no path from the root has more than \(D\) branchings, and since each node has two children the tree has at most \(2^{D+1}-1\) nodes.
For correctness, apply Proposition 7.1 repeatedly: \(X\) is the union of the sets \(X_i\) of the leaves, the nodes that were discarded. A leaf discarded as infeasible is empty. A leaf discarded by integrality had its best point compared with the incumbent. A leaf discarded by bound contains nothing better than the incumbent at the time, and the incumbent’s value never decreases. So no point of \(X\) is better than the final incumbent, which is itself a point of \(X\) .
Example 7.1: Seven linear programs for the cargo problem
Recall the problem: maximize \(5x_1+4x_2\) subject to \(x_1+2x_2\le 8\) , \(3x_1+2x_2\le 11\) , \(x\ge 0\) integer. The objective is integral, so bounds are rounded down. We solve the relaxation of each child as soon as it is created, and explore the child with the larger bound first.
Node 0, the root. \(\bar x=(3/2,13/4)\) with value \(41/2\) ; the bound is \(20\) . Both coordinates are fractional; branch on \(x_1\) , with children \(x_1\le 1\) and \(x_1\ge 2\) .
Node 1, \(x_1\le 1\) . With \(x_1=1\) the floor constraint gives \(x_2=7/2\) : \(\bar x=(1,7/2)\) , value \(19\) .
Node 2, \(x_1\ge 2\) . With \(x_1=2\) the weight constraint gives \(x_2=5/2\) : \(\bar x=(2,5/2)\) , value \(20\) . This node has the larger bound, so it is explored first; branch on \(x_2\) , with children \(x_2\le 2\) and \(x_2\ge 3\) .
Node 3, \(x_1\ge 2\) and \(x_2\le 2\) . With \(x_2=2\) the weight constraint gives \(x_1=7/3\) : \(\bar x=(7/3,2)\) , value \(59/3\) , bound \(19\) .
Node 4, \(x_1\ge 2\) and \(x_2\ge 3\) . The weight would be at least \(6+6=12>11\) . Infeasible; discard.
Node 3 is the only child of node 2 left; branch on \(x_1\) , with children \(x_1\le 2\) and \(x_1\ge 3\) .
Node 5, \(x_1=2\) and \(x_2\le 2\) . \(\bar x=(2,2)\) , value \(18\) , integral.
Node 6, \(x_1\ge 3\) and \(x_2\le 2\) . With \(x_1=3\) the weight constraint gives \(x_2=1\) : \(\bar x=(3,1)\) , value \(19\) , integral.
Both children of node 3 have integral solutions, so both are closed. Node 6, examined first because its value is larger, supplies the incumbent, \(\underline z=19\) ; node 5 offers \(18\) and changes nothing.
Only node 1 remains open. Its bound is \(19\le\underline z\) , so it is pruned by bound without being divided. The list is empty: \(x^\star=(3,1)\) with \(z^\star=19\) , and the search that proves it consisted of seven relaxations.
All three reasons for discarding a node occurred. Notice what the leaves of Figure 7.1 say when read together: every feasible plan has \(x_1\le 1\) , where nothing exceeds \(19\) ; or \(x_1\ge 2\) and \(x_2\ge 3\) , which is impossible; or \(x_1=2\) and \(x_2\le 2\) , where the best is \(18\) ; or \(x_1\ge 3\) and \(x_2\le 2\) , where the best is \(19\) . That is a complete proof of optimality, and the tree is its certificate.
Common mistake. Branching with a gap. After finding \(\bar x_1=3/2\) one must use \(x_1\le 1\) and \(x_1\ge 2\) . Children such as \(x_1\le 1\) and \(x_1\ge 3\) lose every solution with \(x_1=2\) , and in this problem that would do no harm only by luck. The two children must cover every integer value; that is what makes Proposition 7.1 applicable. Equally, a node whose relaxation is integral is always closed, whether or not its value beats the incumbent; dividing it further cannot find anything better inside it.
7.3 A bound that needs no linear programming: knapsack
For some problems the relaxation at a node has a closed-form solution, and branch-and-bound can be run by hand on larger instances.
Definition 7.4 (0–1 knapsack problem). Given items \(j=1,\dots,n\) with positive integer profits \(p_j\) and weights \(w_j\) , and a capacity \(W\) , the 0–1 knapsack problem is
Proposition 7.5 (the greedy solution of the knapsack relaxation). Number the items so that \(p_1/w_1\ge p_2/w_2\ge\dots\ge p_n/w_n\) , and suppose \(\sum_jw_j>W\) . Let \(s\) be the first index with \(w_1+\dots+w_s>W\) , the critical item. Then an optimal solution of the relaxation, in which \(0\le x_j\le 1\) , is
Proof. Let \(\lambda=p_s/w_s\) . For any \(x\) feasible for the relaxation, write
For \(j<s\) the coefficient \(p_j-\lambda w_j\) is nonnegative and \(x_j\le 1\) ; for \(j>s\) it is nonpositive and \(x_j\ge 0\) ; for \(j=s\) it is zero. So the first sum is at most \(\sum_{j<s}(p_j-\lambda w_j)\) . The second term is at most \(\lambda W\) . The greedy solution attains both bounds: it has \(x_j=1\) for \(j<s\) , \(x_j=0\) for \(j>s\) , and total weight exactly \(W\) .
The resulting value is the Dantzig bound. At a node of the tree some variables are fixed at \(0\) or \(1\) ; the relaxation of the node is a knapsack relaxation in the free variables with the capacity left by the items fixed at \(1\) , so the same greedy rule gives its bound. If the fixed items already exceed the capacity, the node is infeasible. The fractional variable, on which we branch, is always the critical item.
Example 7.2: A knapsack tree with thirteen nodes
Take the four items of Example 1.3 in order of profit per unit weight:
| Item | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Profit \(p_j\) | \(23\) | \(24\) | \(15\) | \(13\) |
| Weight \(w_j\) | \(11\) | \(12\) | \(8\) | \(7\) |
| Ratio \(p_j/w_j\) | \(2.09\) | \(2.00\) | \(1.88\) | \(1.86\) |
The capacity is \(W=26\) . Explore depth first, taking the child with the critical variable set to \(1\) before the child with it set to \(0\) , and round bounds down.
| Node | Fixed | Relaxation solution | Value | Outcome |
|---|---|---|---|---|
| 0 | none | \((1,1,\tfrac38,0)\) | \(52.625\) | branch on \(x_3\) |
| 1 | \(x_3=1\) | \((1,\tfrac7{12},1,0)\) | \(52\) | branch on \(x_2\) |
| 2 | \(x_3=1,x_2=1\) | \((\tfrac6{11},1,1,0)\) | \(51.55\) | branch on \(x_1\) |
| 3 | \(x_3=x_2=x_1=1\) | weight \(31\) | none | infeasible |
| 4 | \(x_3=x_2=1,x_1=0\) | \((0,1,1,\tfrac67)\) | \(50.14\) | branch on \(x_4\) |
| 5 | node 4 and \(x_4=1\) | weight \(27\) | none | infeasible |
| 6 | node 4 and \(x_4=0\) | \((0,1,1,0)\) | \(39\) | integral, incumbent \(39\) |
| 7 | \(x_3=1,x_2=0\) | \((1,0,1,1)\) | \(51\) | integral, incumbent \(51\) |
| 8 | \(x_3=0\) | \((1,1,0,\tfrac37)\) | \(52.57\) | branch on \(x_4\) |
| 9 | \(x_3=0,x_4=1\) | \((1,\tfrac23,0,1)\) | \(52\) | branch on \(x_2\) |
| 10 | \(x_3=0,x_4=1,x_2=1\) | \((\tfrac7{11},1,0,1)\) | \(51.64\) | pruned: \(\lfloor 51.64\rfloor\le 51\) |
| 11 | \(x_3=0,x_4=1,x_2=0\) | \((1,0,0,1)\) | \(36\) | pruned: \(36\le 51\) |
| 12 | \(x_3=0,x_4=0\) | \((1,1,0,0)\) | \(47\) | pruned: \(47\le 51\) |
To check one row: at node 1 the item fixed at \(1\) uses \(8\) units, leaving \(18\) . Item 1 fits, leaving \(7\) , and item 2 is critical with \(x_2=7/12\) . The value is \(15+23+24\cdot\tfrac7{12}=52\) .
The optimum is \(x^\star=(1,0,1,1)\) with profit \(23+15+13=51\) and weight exactly \(26\) . It omits item 2, which has the second best ratio, and it was found at node 7 only after the search had backed out of the subtree in which item 2 is taken. The plain greedy choice, items 1 and 2, is worth \(47\) . Thirteen nodes were evaluated out of the \(31\) in the complete tree for four binary variables, and at node 10 the rounding of the bound was needed: without it the node would have been divided.
7.4 The order of exploration
The algorithm leaves open which node to take from the list. The two classical rules are depth-first, which takes the most recently created node and so dives quickly to a feasible solution and keeps the list short, and best-first, which takes an open node with the largest bound. At any moment the list of open nodes also yields a bound on the whole problem.
Proposition 7.6 (the global bounds). At any stage of the algorithm, let \(\underline z\) be the incumbent value and let \(\bar z\) be the largest of \(\underline z\) and the bounds of the open nodes, where a node whose relaxation has not yet been solved carries its parent’s bound. Then \(\underline z\le z^\star\le\bar z\) .
Proof. The left inequality holds because the incumbent is feasible. For the right one, every point of \(X\) lies in a discarded node or in an open node. Points of discarded nodes have value at most \(\underline z\) , by Proposition 7.2. Points of an open node have value at most that node’s bound, and a child’s bound is at most its parent’s.
The difference \(\bar z-\underline z\) is the optimality gap. It shrinks from both sides as the search runs, and it gives a guarantee at any moment: stopping early with the incumbent costs at most the gap. Practical solvers report it continuously and are routinely stopped when it falls below a tolerance.
Proposition 7.7 (best-first wastes no branching). Under best-first selection, with relaxations solved when nodes are created, no node whose bound is smaller than \(z^\star\) is ever divided.
Proof. Suppose the node selected for division has bound \(\beta<z^\star\) . It has the largest bound among open nodes, so by Proposition 7.6, \(z^\star\le\max\{\underline z,\beta\}\) . Since \(\beta<z^\star\) , this forces \(\underline z\ge z^\star\) , hence \(\underline z=z^\star>\beta\) , and the node is pruned by bound and not divided.
Example 7.3: The same problem, depth first
Run the cargo problem again, this time depth first, always taking the child \(x_j\le\lfloor\bar x_j\rfloor\) before its sibling, and solving a relaxation only when its node is taken from the list.
The root gives \((3/2,13/4)\) , bound \(20\) . Its left child \(x_1\le 1\) gives \((1,7/2)\) with value \(19\) ; branch on \(x_2\) . The child \(x_2\le 3\) gives \((1,3)\) with value \(17\) , integral: incumbent \(17\) . Its sibling \(x_2\ge 4\) gives \((0,4)\) with value \(16\le 17\) : pruned by bound. Back at the root’s right child, \(x_1\ge 2\) gives \((2,5/2)\) , value \(20\) ; branch on \(x_2\) . The child \(x_2\le 2\) gives \((7/3,2)\) , value \(59/3\) ; branch on \(x_1\) . The child \(x_1\le 2\) gives \((2,2)\) , value \(18\) : incumbent \(18\) . Its sibling \(x_1\ge 3\) gives \((3,1)\) , value \(19\) : incumbent \(19\) . Finally \(x_1\ge 2\) , \(x_2\ge 3\) is infeasible.
That is nine nodes against seven. The two extra nodes are the children of \(x_1\le 1\) , a node whose bound of \(19\) equals \(z^\star\) ; best-first never divided it because by the time it was reconsidered the incumbent had reached \(19\) . The global bounds tell the story: after the third node the incumbent was \(17\) and the open node \(x_1\ge 2\) carried the root’s bound, so \(17\le z^\star\le 20\) , a gap of \(3\) ; after \((2,2)\) was found, \(18\le z^\star\le 20\) ; after \((3,1)\) , \(19\le z^\star\le 19\) once the last open node was found infeasible.
Depth-first has compensations. It found a feasible plan at its third node, where the bound-driven order of Example 7.1 found none until the last two of its seven relaxations, and it never held more than three open nodes. Solvers mix the two: dive to obtain incumbents, then select by bound to raise the proof.
7.5 When the bound does not move
Everything depends on bounds that tighten as variables are fixed. The following family shows what happens when they do not.
Example 7.4: A family that defeats the relaxation
For odd \(n\) , consider
The left side of the constraint is even and \(n\) is odd, so at most \((n-1)/2\) variables can equal one and \(z^\star=n-1\) . The relaxation sets variables to one until the capacity \(n\) is exhausted, the last one at \(\tfrac12\) , and has value \(n\) . Rounding down does not help, since \(n\) is an integer.
Now fix some variables. As long as the variables fixed at \(1\) number at most \((n-1)/2\) and enough variables remain free to fill the capacity, the relaxation of the node again has value \(n\) : it simply uses free variables instead. No node is pruned by bound until so many variables are fixed that the relaxation becomes integral or infeasible, and that happens only about halfway down the tree. Running the depth-first algorithm of Example 7.2 on this family gives:
| \(n\) | \(5\) | \(7\) | \(9\) | \(11\) | \(13\) | \(15\) |
|---|---|---|---|---|---|---|
| Nodes evaluated | \(39\) | \(139\) | \(503\) | \(1847\) | \(6863\) | \(25739\) |
Each increase of \(n\) by two multiplies the work by nearly four. Yet the problem is trivial for a human, by the parity argument above, and it becomes trivial for the algorithm once that argument is given to it as a constraint: dividing the constraint by \(2\) and rounding the right side down gives \(\sum_jx_j\le(n-1)/2\) , with which the relaxation has value \(n-1\) at the root and the root’s solution is integral. One node.
The remedy for a stagnant bound is a better formulation, and the rounding step just used is the first example of a cutting plane. Chapter 8 develops it. Modern solvers interleave the two ideas: at each node they add cutting planes before deciding to branch, a combination called branch-and-cut. They also spend effort on the choice of branching variable, preferring one whose two children both have much smaller bounds, and on heuristics that find good incumbents early so that pruning by bound starts sooner. None of this changes the logic of Propositions 7.1 and 7.2; it changes how soon the two global bounds meet.
One further caution concerns what a finished tree proves. The answer of branch-and-bound is certified by the whole tree, not by the final incumbent alone, and that certificate can be large. For the problems of Chapters 2 to 4 a certificate was a potential, a cut, or a cover, checkable in one pass over the data. For NP-hard problems no short certificate of optimality is expected to exist in general, and the tree is the price.
Exercises
-
Solve by branch-and-bound, solving each relaxation graphically or by the active-constraint method of Theorem 6.1: maximize \(4x_1+3x_2\) subject to \(2x_1+x_2\le 7\) , \(x_1+2x_2\le 7\) , \(x\ge 0\) integer. Branch first on \(x_1\) , explore the child \(x_1\le\lfloor\bar x_1\rfloor\) first, and record every node with its relaxation solution, bound, and outcome.
Solution
The objective is integral, so bounds are rounded down.
Node 0. Both constraints are active at the relaxation optimum: subtracting twice the second from the first gives \(-3x_2=-7\) , so \(\bar x=(7/3,7/3)\) with value \(49/3\) , bound \(16\) . Branch on \(x_1\) .
Node 1, \(x_1\le 2\) . With \(x_1=2\) the second constraint gives \(x_2=5/2\) (the first allows \(3\) ): \(\bar x=(2,5/2)\) , value \(31/2\) , bound \(15\) . Branch on \(x_2\) .
Node 2, \(x_1\le 2\) , \(x_2\le 2\) . \(\bar x=(2,2)\) , value \(14\) , integral. Incumbent \(14\) .
Node 3, \(x_1\le 2\) , \(x_2\ge 3\) . With \(x_2=3\) the second constraint gives \(x_1=1\) : \(\bar x=(1,3)\) , value \(13\le 14\) . Pruned by bound; it is also integral.
Node 4, \(x_1\ge 3\) . With \(x_1=3\) the first constraint gives \(x_2=1\) : \(\bar x=(3,1)\) , value \(15\) , integral. Incumbent \(15\) .
No open nodes remain. The optimum is \(x^\star=(3,1)\) with \(z^\star=15\) , found with five relaxations. The leaves prove it: plans with \(x_1\le 2\) and \(x_2\le 2\) are worth at most \(14\) ; with \(x_1\le 2\) and \(x_2\ge 3\) at most \(13\) ; with \(x_1\ge 3\) at most \(15\) . Note that the optimum is again not a rounding of \((7/3,7/3)\) : the nearest integer point \((2,2)\) is worth \(14\) .
-
A partially explored tree for a maximization problem with integer objective coefficients has incumbent value \(41\) and four open nodes with relaxation values \(46.8\) , \(43.2\) , \(41.9\) , and \(40.5\) . State the global bounds of Proposition 7.6 and the optimality gap, say which open nodes can be discarded now, and say what happens to each remaining node if a solution of value \(43\) is found.
Answer
The rounded bounds of the open nodes are \(46\) , \(43\) , \(41\) , and \(40\) . So \(41\le z^\star\le 46\) , a gap of \(5\) . The nodes with values \(41.9\) and \(40.5\) can be discarded now, since \(41\le 41\) and \(40\le 41\) . If a solution of value \(43\) is found, the node with value \(43.2\) is discarded as well, since \(43\le 43\) ; only the node with value \(46.8\) remains, and \(43\le z^\star\le 46\) .
-
For the knapsack instance of Example 7.2 compute the Dantzig bound of the node in which \(x_1=0\) and \(x_2=1\) are fixed and the other items are free, giving the relaxation solution, and say whether the node would be pruned when the incumbent is \(51\) .
Solution
Items are numbered as in Example 7.2: profits \((23,24,15,13)\) , weights \((11,12,8,7)\) , capacity \(26\) . With \(x_2=1\) fixed, the remaining capacity is \(26-12=14\) , and with \(x_1=0\) fixed the free items are \(3\) and \(4\) , already in order of ratio.
Item 3 has weight \(8\le 14\) , so \(x_3=1\) and \(6\) units remain. Item 4 has weight \(7>6\) , so it is critical and \(x_4=6/7\) . The relaxation solution is \((0,1,1,\tfrac67)\) and the Dantzig bound is
\[ 24+15+13\cdot\tfrac67=39+\tfrac{78}{7}\approx 50.14 . \]Rounded down, the bound is \(50\) . With an incumbent of \(51\) the node is pruned by bound, since \(50\le 51\) : no selection that takes item 2 and leaves out item 1 can be worth more than \(50\) . This is node 4 of the table in Example 7.2, reached there before any incumbent existed, which is why it was divided in that run. The order in which nodes are visited changes which of them are pruned.
-
Solve the knapsack problem with profits \((16,15,12,5)\) , weights \((4,5,6,3)\) , and capacity \(10\) by branch-and-bound with Dantzig bounds, depth first with the critical variable set to \(1\) first; give the table of nodes.
Solution
The ratios are \(4\) , \(3\) , \(2\) , and \(5/3\) , so the items are already in order.
Node Fixed Relaxation solution Value Outcome 0 none \((1,1,\tfrac16,0)\) \(33\) branch on \(x_3\) 1 \(x_3=1\) \((1,0,1,0)\) \(28\) integral, incumbent \(28\) 2 \(x_3=0\) \((1,1,0,\tfrac13)\) \(32.67\) branch on \(x_4\) 3 \(x_3=0,x_4=1\) \((1,\tfrac35,0,1)\) \(30\) branch on \(x_2\) 4 \(x_3=0,x_4=1,x_2=1\) \((\tfrac12,1,0,1)\) \(28\) pruned: \(28\le 28\) 5 \(x_3=0,x_4=1,x_2=0\) \((1,0,0,1)\) \(21\) pruned: \(21\le 28\) 6 \(x_3=0,x_4=0\) \((1,1,0,0)\) \(31\) integral, incumbent \(31\) At the root, items 1 and 2 use \(9\) of the \(10\) units and item 3 is critical with \(x_3=1/6\) , value \(16+15+2=33\) . At node 1, item 3 uses \(6\) , item 1 fits in the remaining \(4\) , and nothing is left, so the relaxation is integral with value \(28\) . At node 3, item 4 uses \(3\) , item 1 uses \(4\) , and item 2 is critical with \(x_2=3/5\) : \(5+16+9=30\) . At node 4 the fixed items use \(8\) and item 1 is critical with \(x_1=1/2\) : \(5+15+8=28\) .
The optimum is items 1 and 2, with profit \(31\) and weight \(9\) . Seven nodes were evaluated.
-
Prove that in the branch-and-bound algorithm the relaxation value of a child never exceeds that of its parent, and deduce that along any path from the root the bounds are nonincreasing.
Solution
Let a node have relaxation feasible region \(Q\) and let a child have region \(Q'=Q\cap\{x:x_j\le\lfloor\bar x_j\rfloor\}\) or \(Q'=Q\cap\{x:x_j\ge\lceil\bar x_j\rceil\}\) . In both cases \(Q'\subseteq Q\) . If \(Q'\) is empty the child is infeasible and has no relaxation value, or the value \(-\infty\) by convention. Otherwise every point of \(Q'\) is a point of \(Q\) , so
\[ \max\{c^{\top}x:x\in Q'\}\le\max\{c^{\top}x:x\in Q\}. \]That is the first claim. For the second, consider a path from the root through nodes with regions \(Q_0\supseteq Q_1\supseteq Q_2\supseteq\dots\) . Applying the first claim to each consecutive pair shows that the relaxation values form a nonincreasing sequence. Rounding down preserves the order, so the rounded bounds are nonincreasing as well.
A consequence used in Proposition 7.6: an open node whose relaxation has not been solved may be given its parent’s bound, which is valid for it. In Example 7.1 the values along the path through nodes \(0,2,3,6\) are \(41/2\) , \(20\) , \(59/3\) , \(19\) .
-
State the analogues of Propositions 7.2 and 7.6 for a minimization problem, taking care with the direction of every inequality and with the direction of rounding when the objective is integral.
Hint
For minimization the incumbent value \(\bar z\) is an upper bound and each node’s relaxation gives a lower bound \(\underline z_i\le z_i^\star\) . Prune by bound when \(\underline z_i\ge\bar z\) , or, with an integral objective, when \(\lceil\underline z_i\rceil\ge\bar z\) . The global bounds are \(\min\{\bar z,\min_i\underline z_i\}\le z^\star\le\bar z\) over open nodes \(i\) . Rounding goes up, not down.
-
Explain what is wrong with each of these two actions of a student running branch-and-bound on a maximization problem: (a) after a relaxation gives \(\bar x_2=2.6\) , creating the children \(x_2\le 2\) and \(x_2\ge 4\) “to move faster”; (b) declining to close a node whose relaxation solution is integral with value \(30\) because the incumbent is \(33\) and “there may be better points deeper in the node”.
Answer
(a) The children \(x_2\le 2\) and \(x_2\ge 4\) omit every solution with \(x_2=3\) ; their union is not the node, so Proposition 7.1 no longer applies and the optimum may be lost. The correct children are \(x_2\le 2\) and \(x_2\ge 3\) . (b) An integral relaxation solution is optimal for its node by Proposition 7.2(c); nothing in the node is worth more than \(30\) , so the node is closed. It is also pruned by bound, since \(30\le 33\) .
-
Prove that when a node’s relaxation solution has \(\bar x_j\) fractional, the two children \(x_j\le\lfloor\bar x_j\rfloor\) and \(x_j\ge\lceil\bar x_j\rceil\) have disjoint feasible sets whose union contains every integer point of the node, and that \(\bar x\) belongs to neither.
Solution
Let \(Q\) be the set of integer points of the node, and let \(f=\lfloor\bar x_j\rfloor\) . Because \(\bar x_j\) is not an integer, \(f<\bar x_j<f+1\) and \(\lceil\bar x_j\rceil=f+1\) .
Cover. For any integer point \(x\in Q\) the coordinate \(x_j\) is an integer, so either \(x_j\le f\) or \(x_j\ge f+1\) ; there is no integer strictly between \(f\) and \(f+1\) . Hence \(x\) belongs to one of the children.
Disjoint. No point can satisfy both \(x_j\le f\) and \(x_j\ge f+1\) .
The fractional point is excluded. \(\bar x_j>f\) violates the first child’s constraint and \(\bar x_j<f+1\) violates the second’s.
So the children partition the integer points of the node and both exclude \(\bar x\) . The first two facts make Proposition 7.1 applicable with no solution counted twice; the third guarantees progress, since each child’s relaxation must have an optimal solution different from \(\bar x\) . The argument uses integrality of \(x_j\) only, so it applies equally to general integer variables and to binary ones, where the children are \(x_j=0\) and \(x_j=1\) .
-
For the family of Example 7.4 with \(n=3\) , draw the complete depth-first tree with the critical variable set to \(1\) first, and verify the count of \(11\) nodes; identify which leaves are infeasible and which are integral.
Solution
With \(n=3\) the problem is to maximize \(2(x_1+x_2+x_3)\) subject to \(2(x_1+x_2+x_3)\le 3\) . All ratios are equal, so the greedy rule takes free items in index order.
Node 0: \((1,\tfrac12,0)\) , value \(3\) ; branch on \(x_2\) . Node 1, \(x_2=1\) : one unit remains, so \((\tfrac12,1,0)\) , value \(3\) ; branch on \(x_1\) . Node 2, \(x_2=x_1=1\) : weight \(4>3\) , infeasible. Node 3, \(x_2=1\) , \(x_1=0\) : \((0,1,\tfrac12)\) , value \(3\) ; branch on \(x_3\) . Node 4, adding \(x_3=1\) : weight \(4\) , infeasible. Node 5, adding \(x_3=0\) : \((0,1,0)\) , value \(2\) , integral; incumbent \(2\) . Node 6, \(x_2=0\) : \((1,0,\tfrac12)\) , value \(3>2\) ; branch on \(x_3\) . Node 7, \(x_2=0\) , \(x_3=1\) : \((\tfrac12,0,1)\) , value \(3\) ; branch on \(x_1\) . Node 8, adding \(x_1=1\) : infeasible. Node 9, adding \(x_1=0\) : \((0,0,1)\) , value \(2\) , integral, no improvement. Node 10, \(x_2=0\) , \(x_3=0\) : \((1,0,0)\) , value \(2\) , integral, no improvement.
That is \(11\) nodes: five were divided, three were infeasible (nodes 2, 4, 8) and three were integral (nodes 5, 9, 10). Not one was pruned by bound before becoming integral: every fractional node had bound \(3\) , above the optimum \(2\) , exactly as Example 7.4 describes.
-
Compare depth-first and best-first selection with respect to (a) the number of open nodes that must be stored, (b) how early an incumbent is found, and (c) the guarantee of Proposition 7.7, and explain why a solver might switch from one to the other during a run.
Hint
(a) Depth-first keeps roughly one unexplored sibling per level of the current path, so its list grows with the depth of the tree; best-first may keep a list that grows with the number of nodes. (b) Depth-first reaches leaves, and hence feasible solutions, after few nodes; best-first may reach them late. (c) Proposition 7.7 holds for best-first only; depth-first can divide nodes whose bound is below \(z^\star\) , as in Example 7.3. A solver dives first to obtain an incumbent, then selects by bound so that pruning is as effective as possible.
-
Give an example of a node bound and an incumbent value for which the node is pruned when the objective is known to be integral and not pruned otherwise, and identify the node of Example 7.2 at which this occurred.
Answer
A node with relaxation value \(51.64\) and incumbent \(51\) : with an integral objective the bound is \(\lfloor 51.64\rfloor=51\le 51\) and the node is pruned; without that knowledge \(51.64>51\) and it must be divided. This is node 10 of Example 7.2.
-
A travelling salesman problem on four cities has costs \(c_{12}=2\) , \(c_{13}=7\) , \(c_{14}=6\) , \(c_{21}=2\) , \(c_{23}=5\) , \(c_{24}=8\) , \(c_{31}=6\) , \(c_{32}=7\) , \(c_{34}=3\) , \(c_{41}=5\) , \(c_{42}=8\) , \(c_{43}=3\) . Use the assignment problem of Chapter 4 as the relaxation: find its optimal solution and value, observe that it consists of two subtours, branch by forbidding in turn each of the two arcs of one subtour, and solve the problem.
Solution
Root. The assignment relaxation ignores the requirement of a single tour. Its optimal solution pairs the cities off: \(1\) to \(2\) , \(2\) to \(1\) , \(3\) to \(4\) , \(4\) to \(3\) , at cost \(2+2+3+3=10\) . Every city is left once and entered once, but the solution consists of the two subtours \(1,2,1\) and \(3,4,3\) . So \(10\) is a lower bound on the length of a tour, and the root is not closed.
Branching. A tour cannot use both arcs of the subtour \(1,2,1\) , so every tour either avoids the arc from \(1\) to \(2\) or avoids the arc from \(2\) to \(1\) . These two children cover all tours.
Child A: the arc from \(2\) to \(1\) is forbidden. The best assignment is now \(1\) to \(2\) , \(2\) to \(3\) , \(3\) to \(4\) , \(4\) to \(1\) , at cost \(2+5+3+5=15\) . It is a single tour, so it is feasible for the travelling salesman problem: incumbent \(15\) , and the node is closed.
Child B: the arc from \(1\) to \(2\) is forbidden. The best assignment is \(1\) to \(4\) , \(4\) to \(3\) , \(3\) to \(2\) , \(2\) to \(1\) , at cost \(6+3+7+2=18\) . Its bound \(18\ge 15\) , so for this minimization problem the node is pruned by bound; it happens also to be a tour.
The optimal tour is \(1,2,3,4,1\) with length \(15\) , found with three assignment problems. Listing all six tours confirms it: their lengths are \(15\) , \(18\) , \(19\) , \(20\) , \(25\) , and \(27\) .
-
Add the inequality \(x_1+x_2\le 4\) of Example 5.1 to the cargo problem and run branch-and-bound again. How many nodes are needed, and what does this say about the relation between formulation strength and tree size?
Hint
One node. With the added inequality the root relaxation has the optimal solution \((3,1)\) , which is integral, so Proposition 7.2(c) closes the root. Compare seven nodes for the original formulation: a stronger formulation is a smaller tree.
-
Prove that the complete enumeration tree for \(n\) binary variables, in which every node at depth less than \(n\) has two children, has \(2^{n+1}-1\) nodes, and compute the fraction of that tree evaluated in Example 7.2.
Answer
There are \(2^d\) nodes at depth \(d\) , so the total is \(1+2+\dots+2^n=2^{n+1}-1\) . For \(n=4\) that is \(31\) , and Example 7.2 evaluated \(13\) of them, about \(42\) percent.
-
In a mixed-integer program only some variables are required to be integers. Explain how the branching rule and Proposition 7.2(c) must be modified, and apply your rule to decide what to do at a node whose relaxation solution is \((x_1,x_2,y)=(2,1.5,0.7)\) when \(x_1,x_2\) are integer variables and \(y\) is continuous.
Hint
Branch only on integer variables with fractional values, and close a node by integrality when every integer variable is integral in the relaxation solution, whatever the continuous variables are. Here \(x_2=1.5\) is fractional: create the children \(x_2\le 1\) and \(x_2\ge 2\) . The value \(y=0.7\) is irrelevant.
-
Using Proposition 7.6, show that if branch-and-bound is stopped as soon as \(\bar z-\underline z\le\varepsilon\,\underline z\) with \(\underline z>0\) , the incumbent has value at least \(z^\star/(1+\varepsilon)\) .
Solution
At the moment of stopping, Proposition 7.6 gives \(z^\star\le\bar z\) , and the stopping rule gives \(\bar z\le\underline z+\varepsilon\underline z=(1+\varepsilon)\underline z\) . Combining,
\[ z^\star\le(1+\varepsilon)\,\underline z,\qquad\text{that is,}\qquad \underline z\ge\frac{z^\star}{1+\varepsilon}. \]The incumbent is feasible, so its value \(\underline z\) is the value of a solution one can actually use, and it is within a factor \(1+\varepsilon\) of optimal. For instance, with \(\varepsilon=0.01\) the incumbent is worth at least \(99\) percent of the optimum, since \(1/1.01>0.99\) .
Two points deserve notice. The guarantee is computed from quantities the algorithm has, \(\bar z\) and \(\underline z\) ; it does not require knowing \(z^\star\) . And the guarantee is a posteriori, specific to the instance and the moment of stopping, unlike the a priori worst-case ratios of Chapter 10. If the gap stops shrinking, as in Example 7.4 where \(\bar z\) stays at \(n\) , the guarantee stays weak however long the search runs.
-
Classify the worst-case number of nodes of branch-and-bound on binary programs as a function of the number of variables, using Example 7.4 for a lower bound and Exercise 14 for an upper bound, and say whether this contradicts or agrees with Proposition 1.11.
Hint
Exponential in both directions: at most \(2^{n+1}-1\) nodes by Exercise 7.14, and at least a number growing by a factor of nearly \(4\) for each two additional variables on the family of Example 7.4. This agrees with Proposition 1.11: a polynomial bound on the tree would give a polynomial algorithm for an NP-hard problem.
-
Using the Dantzig bound and one feasible solution, show without any branching that the knapsack instance with profits \((10,12,7)\) , weights \((4,6,5)\) , and capacity \(10\) has optimal value \(22\) .
Solution
The ratios are \(10/4=2.5\) , \(12/6=2\) , and \(7/5=1.4\) , so the items are in order. The greedy rule of Proposition 7.5 takes item 1, using \(4\) units, then item 2, using \(6\) more; the capacity \(10\) is exactly exhausted. Item 3 is the critical item and receives \(x_3=0/5=0\) . The relaxation solution is \((1,1,0)\) with value \(10+12=22\) , so the Dantzig bound is \(22\) .
The solution \((1,1,0)\) is itself a feasible integer solution, with weight \(10\le 10\) and profit \(22\) . So \(22\le z^\star\le 22\) and the optimal value is \(22\) . In the language of this chapter the root node is closed by integrality and the tree has one node.
No other argument is needed, but it is worth seeing why the instance is so easy: the items of best ratio happen to fill the knapsack exactly. Change the capacity to \(11\) and the relaxation becomes \((1,1,\tfrac15)\) with value \(23.4\) ; the bound \(23\) no longer matches the best selection, which is still worth \(22\) , and branching is required to prove it.