Branch-and-cut

Part 3 · Exact methods · Chapter 8 · Lecture notes, volume 2 (PDF) · Exercises: Branch-and-cut

Prerequisites

• From this module, the chapters «Valid inequalities» and «Cover inequalities»: valid inequalities, and the separation of a violated inequality of a family.

• From this module, the chapter «Cutting plane algorithm»: Gomory fractional cuts, and the re-optimization of the LP problem with the dual simplex algorithm after the insertion of a cut.

• From this module, the chapter «LP-based branch-and-bound»: the list of LP problems, the pruning criteria, and the branching-variable and branching-node selection strategies.

Objectives

At the end of this chapter you will be able to:

• explain how cutting planes and branching operations complement each other;

• distinguish global and local valid inequalities, and say where a cut can be used;

• describe cut-and-branch and branch-and-cut algorithms, and the role of the cut pool;

• execute a cut-and-branch algorithm with Gomory cuts by hand on a small ILP problem and compare the size of the tree with and without cuts;

• generate a local cut at a branching node and re-optimize with the dual simplex algorithm.

8.1 Branch-and-cut algorithms

Definition 8.1: branch-and-cut algorithm

Given an ILP problem in canonical maximization form with integer input data, a branch-and-cut algorithm is a branch-and-bound algorithm in which the LP problems of the branching nodes are strengthened with cutting planes before branching.

• A cutting plane algorithm moves the LP relaxation towards the convex hull of the integer solutions, but Gomory fractional cuts lose effectiveness after the first iterations (tailing off).

• A branch-and-bound algorithm partitions the feasible region into smaller LP problems, but started from a weak LP relaxation it needs a large tree.

Cuts decrease the bounds of the nodes, so more nodes are pruned by bound; branching guarantees termination when the cuts are no longer effective.

• All modern MIP solvers are based on branch-and-cut algorithms (see the chapter «What a MIP solver does»).

8.2 Global and local valid inequalities

• In a branch-and-bound algorithm, the \(\LP_k\) problem of a branching node \(k\) is the LP relaxation with the branching constraints of the path from the root to node \(k\).

• We denote by \(F\) the set of integer feasible solutions of the ILP problem, and by \(F_k \subseteq F\) the set of those that satisfy the branching constraints of node \(k\). At the root node \(F_1 = F\).

Definition 8.2: global and local valid inequalities

A linear inequality \(\vet\alpha\T\vet x \le \beta\) is called:

1. a globally valid inequality (or global cut) if it is satisfied by all the solutions in \(F\);

2. a locally valid inequality for the branching node \(k\) (or local cut) if it is satisfied by all the solutions in \(F_k\).

• Since \(F_k \subseteq F\), every global cut is also a local cut of every node. The converse is false: a local cut can remove integer feasible solutions that belong to other branches of the tree.

• A local cut of node \(k\) is valid for all the nodes of the subtree rooted at \(k\), and it must not be used outside this subtree.

A cut derived only from the original constraints (and from other global cuts) is global. A cut whose derivation uses a branching constraint is, in general, only local.

• A Gomory fractional cut generated at the root node is global: it is derived from the original constraints alone, and so is an inequality of a family (such as the cover inequalities of a constraint with positive coefficients) separated from them. A Gomory fractional cut generated by a row that contains the slack variable of a branching constraint with a non-zero coefficient is treated as local.

8.3 Cut-and-branch and branch-and-cut

Definition 8.3: cut-and-branch algorithm

A cut-and-branch algorithm executes a cutting plane algorithm at the root node for a limited number of rounds of cuts, adds the cuts found to the ILP problem, and then executes a branch-and-bound algorithm on the strengthened problem. No cuts are generated at the other nodes.

• All the root cuts are global: at the root node no branching constraint exists.

• In a branch-and-cut algorithm cuts are generated also at the other nodes (at all of them, or at some of them, for example every ten levels of the tree). The cuts can be global or local.

• At each node, the generation of cuts stops when the solution of the \(\LP_k\) problem is integer or the node can be pruned; when no violated cut is found; when a maximum number of rounds is reached; or when the decrease of \(z(\LP_k)\) in the last rounds is small (tailing off).

8.3.1 The cut pool

• Cuts are stored in a data structure called the cut pool. Before calling the (more expensive) cut-generation procedures, the algorithm checks whether a cut of the pool is violated by \(\tilde{\vet x}(\LP_k)\).

• Global cuts are stored in a global pool, usable at every node. Local cuts are stored with their node and are inherited only by its descendants.

• Each cut adds a constraint to the LP problems. Cuts that stay inactive for many iterations are removed from the LP problem and kept only in the pool.

8.3.2 High-level pseudocode

• The branch-and-cut algorithm has the pseudocode of the branch-and-bound algorithm (same branching operations, same pruning criteria, same list \(L\)): only the Branching Node Solution Sub-Procedure changes.

Algorithm

• Input: An \(\LP_k\) problem associated with a branching node, the cut pool, and a maximum number \(R\) of rounds of cuts.

• Step 1: Bounding operations

  Solve the \(\LP_k\) problem.

  1. if the \(\LP_k\) problem is infeasible, then STOP.

  2. if \(\left\lfloor z(\LP_k) \right\rfloor \le \LB\), then STOP.

  3. if \({\tilde{\vet x}}(\LP_k)\) is integer, then update the lower bound and the incumbent solution, remove from the list \(L\) all LP problems with \(\left\lfloor z(\LP) \right\rfloor \le \LB\) and STOP.

• Step 2: Cut generation

  If \(R\) rounds of cuts have been executed at node \(k\), go to Step 3. Otherwise:

  1. look in the cut pool for cuts violated by \({\tilde{\vet x}}(\LP_k)\); if none is found, generate new violated cuts and store them in the pool (global cuts in the global pool, local cuts with node \(k\));

  2. if no violated cut exists, go to Step 3. Otherwise add the cuts to the \(\LP_k\) problem, re-optimize it and go to Step 1.

• Step 3: Insertion into the list

  Insert the \(\LP_k\) problem (with its cuts) into the list \(L\) and STOP.

• With \(R = 0\) at every node except the root we obtain a cut-and-branch algorithm; with \(R = 0\) at every node we obtain the branch-and-bound algorithm.

• The pseudocode does not say how the cuts are generated or how the LP problem is re-optimized. After the insertion of a cut the dictionary is dual feasible, so the dual simplex algorithm starts from the optimal dictionary of the previous problem, as after a branching constraint.

8.4 Worked example: cut-and-branch with Gomory cuts

• We use the problem \(P10\) of the catalogue of MIP problems: maximize \(5x_1+2x_2\) subject to \(-x_1+3x_2\le 12\), \(x_1+2x_2\le 12\), \(3x_1-2x_2\le 8\), \(x_1,x_2\in\Z_{\ge 0}\). Its unique optimal solution is \(\tilde{\vet x}(\ILP) = (4,4)\), with \(z(\ILP) = 28\).

• The cuts are the Gomory fractional cuts of the chapter on the cutting plane algorithm, with the same rule: the row with the largest fractional right-hand side, and the smallest index in case of a tie.

• Since the data are integer, the bound of a node is \(\lfloor z(\LP_k) \rfloor\). All the executions use the same rules: the smallest-index rule as branching-variable selection strategy, the LIFO rule as branching-node selection strategy, the down-branching node solved first, and \(\LB = -\infty\) at the start.

Example 8.1: branch-and-bound without cuts

The \(\LP_1\) problem is the LP relaxation of \(P10\). An optimal solution is \(\tilde{\vet x}(\LP_1) = (5,\tfrac{7}{2})\), with \(z(\LP_1) = 32\) and \(\UB = 32\). The branch-and-bound algorithm solves \(5\) LP problems:

Node	Parent	Branching	\(\tilde{\vet x}(\LP_k)\)	\(z(\LP_k)\)	\(\LB\)	Outcome
1	–	–	\((5, \tfrac{7}{2})\)	\(32\)	\(-\infty\)	branching on \(x_2\)
2	1	\(x_2 \le 3\)	\((\tfrac{14}{3}, 3)\)	\(\tfrac{88}{3}\)	\(-\infty\)	branching on \(x_1\)
3	1	\(x_2 \ge 4\)	\((4, 4)\)	\(28\)	\(28\)	pruned by integrality
4	2	\(x_1 \le 4\)	\((4, 3)\)	\(26\)	\(28\)	pruned by integrality
5	2	\(x_1 \ge 5\)	–	–	\(28\)	pruned by infeasibility

Example 8.2: cut-and-branch with one Gomory cut

• Root: cut generation. The two rows of the optimal dictionary of \(\LP_1\) with a fractional right-hand side, the rows of \(x_2\) and of \(x_3\), have the same right-hand side \(\frac{1}{2}\); we use the row of \(x_2\), whose index is smaller. With the slack variables \(x_4 = 12 - x_1 - 2x_2\) and \(x_5 = 8 - 3x_1 + 2x_2\) the cut is

  \[ \tfrac{3}{8}\,x_4 + \tfrac{7}{8}\,x_5 \ge \tfrac{1}{2} \qquad\Longleftrightarrow\qquad 3\,x_1 - x_2 \le 11 . \]

  It is a global cut, and it cuts off \(\tilde{\vet x}(\LP_1)\): \(3 \cdot 5 - \frac{7}{2} = \frac{23}{2} > 11\).

• Root: re-optimization. We add the cut to the \(\LP_1\) problem and we re-optimize it with the dual simplex algorithm. An optimal solution is

  \[ \tilde{\vet x}(\LP_1) = (\tfrac{34}{7},\tfrac{25}{7}), \qquad z(\LP_1) = \tfrac{220}{7}, \qquad \UB = 31 . \]

• Branch-and-bound. The branch-and-bound algorithm now starts from this \(\LP_1\) problem. Every node inherits the cut. It solves \(3\) LP problems instead of \(5\):

Node	Parent	Branching	\(\tilde{\vet x}(\LP_k)\)	\(z(\LP_k)\)	\(\LB\)	Outcome
1	–	–	\((\tfrac{34}{7}, \tfrac{25}{7})\)	\(\tfrac{220}{7}\)	\(-\infty\)	branching on \(x_1\)
2	1	\(x_1 \le 4\)	\((4, 4)\)	\(28\)	\(28\)	pruned by integrality
3	1	\(x_1 \ge 5\)	–	–	\(28\)	pruned by infeasibility

• One Gomory cut reduces the number of LP problems from \(5\) to \(3\). The cut does not find the optimal solution: it moves the optimal solution of the root LP problem, so that the algorithm branches on \(x_1\) and the node \(x_1 \le 4\) gives the optimal solution at once.

• A second round of cuts, in the same cut-and-branch algorithm, gives an integer solution at the root. The row of \(x_1\) has the largest right-hand side \(\frac{6}{7}\); with the slack variable \(x_6 = 11 - 3x_1 + x_2\) of the first cut the new cut is

  \[ \tfrac{1}{7}\,x_4 + \tfrac{2}{7}\,x_6 \ge \tfrac{6}{7} \qquad\Longleftrightarrow\qquad x_1 \le 4 . \]

• The optimal solution of the new \(\LP_1\) problem is \((4,4)\), with \(z(\LP_1) = 28\). The node is pruned by integrality, and the algorithm stops with \(\LB = \UB = 28\) after solving one LP problem.

Cuts added at the root	\(z(\LP_1)\)	\(\UB\) at the root	LP problems solved
none (branch-and-bound)	\(32\)	\(32\)	\(5\)
\(3 \, x_1 - x_2 \le 11\)	\(\tfrac{220}{7}\)	\(31\)	\(3\)
\(3 \, x_1 - x_2 \le 11\) and \(x_1 \le 4\)	\(28\)	\(28\)	\(1\)

• The stronger the cuts, the smaller the tree, until it reduces to the root node.

• This is not the rule. The table below reports the same algorithm on the problem \(P2\) of the catalogue (maximize \(x_1+3x_2\) subject to \(-4x_1+10x_2\le 35\), \(3x_1+x_2\le 12\), \(x_1,x_2\in\Z_{\ge 0}\), with \(z(\ILP) = 14\)) for an increasing number of rounds of Gomory cuts.

Rounds	Last cut added	\(z(\LP_1)\)	\(\UB\) at the root	LP problems solved
\(0\)	–	\(16\)	\(16\)	\(4\)
\(1\)	\(-3 \, x_1 + 10 \, x_2 \le 37\)	\(\tfrac{524}{33}\)	\(15\)	\(4\)
\(2\)	\(x_1 + 3 \, x_2 \le 15\)	\(15\)	\(15\)	\(4\)
\(3\)	\(-x_1 + 5 \, x_2 \le 19\)	\(15\)	\(15\)	\(4\)
\(4\)	\(x_2 \le 4\)	\(\tfrac{44}{3}\)	\(14\)	\(2\)
\(5\)	\(x_1 + x_2 \le 6\)	\(14\)	\(14\)	\(1\)

• The first three cuts decrease \(z(\LP_1)\) from \(16\) to \(15\) but the tree has always \(4\) nodes; \(5\) rounds are needed to reach the root node. The upper bound improves slowly, as in the tailing off of the cutting plane algorithm.

• A cut-and-branch algorithm must decide when to stop cutting and start branching: the cost of each round is paid at every node of the tree.

8.5 Local cuts: an example

• We use the car example (\(x_1\) sports cars and \(x_2\) family cars): maximize \(3x_1+2x_2\) subject to \(10x_1+4x_2\le 45\), \(4x_1+14x_2\le 49\), \(x_1,x_2\in\Z_{\ge 0}\). In the branch-and-bound algorithm without cuts, node \(3\) is the up-branching child of the root, with the branching constraint \(x_1 \ge 4\) and the slack variable \(x_5 = x_1 - 4\).

• The optimal dictionary of the \(\LP_3\) problem, with \(\tilde{\vet x}(\LP_3) = (4,\tfrac{5}{4})\) and \(z(\LP_3) = \tfrac{29}{2}\), is:

\[\begin{equation*} \begin{cases} \begin{array}{rrrrrrr} {x_1} & {=} & {4} & & & {+} & {x_5} \\[2ex] {x_2} & {=} & {\dfrac{5}{4}} & {-} & {\dfrac{1}{4}}\, {x_3} & {-} & {\dfrac{5}{2}}\, {x_5} \\[2ex] {x_4} & {=} & {\dfrac{31}{2}} & {+} & {\dfrac{7}{2}}\, {x_3} & {+} & {31}\, {x_5} \\[2ex] {z} & {=} & {\dfrac{29}{2}} & {-} & {\dfrac{1}{2}}\, {x_3} & {-} & {2}\, {x_5} \end{array} \end{cases} \end{equation*}\]

Example 8.3: a local cut at node 3

• A simple local cut. From \(10\,x_1 + 4\,x_2 \le 45\) and the branching constraint \(x_1 \ge 4\) we have

  \[ 4\,x_2 \le 45 - 10\,x_1 \le 45 - 10 \cdot 4 = 5 \quad\Longrightarrow\quad x_2 \le \tfrac{5}{4} \quad\Longrightarrow\quad x_2 \le 1 . \]

• The inequality \(x_2 \le 1\) is valid for all the solutions in \(F_3\), but it is not globally valid: the integer feasible solution \((3,2)\), of value \(13\), violates it. It is a local cut of node \(3\).

• We add it to the \(\LP_3\) problem, with the slack variable \(x_6 = 1 - x_2\), and we re-optimize.

• The cut is inserted with the slack variable \(x_6 \ge 0\). The new row is

  \[ x_6 = -\dfrac{1}{4} + \dfrac{1}{4} \, x_3 + \dfrac{5}{2} \, x_5. \]

• The dictionary below is dual feasible but not primal feasible, since \(\bar b_{6} = -\dfrac{1}{4} < 0\):

\[\begin{equation*} \begin{cases} \begin{array}{rrrrrrr} {x_1} & {=} & {4} & & & {+} & {x_5} \\[2ex] {x_2} & {=} & {\dfrac{5}{4}} & {-} & {\dfrac{1}{4}}\, {x_3} & {-} & {\dfrac{5}{2}}\, {x_5} \\[2ex] {x_4} & {=} & {\dfrac{31}{2}} & {+} & {\dfrac{7}{2}}\, {x_3} & {+} & {31}\, {x_5} \\[2ex] {x_6} & {=} & {-\dfrac{1}{4}} & {+} & {\dfrac{1}{4}}\, {x_3} & {+} & {\dfrac{5}{2}}\, {x_5} \\[2ex] {z} & {=} & {\dfrac{29}{2}} & {-} & {\dfrac{1}{2}}\, {x_3} & {-} & {2}\, {x_5} \end{array} \end{cases} \end{equation*}\]

• Dual pivoting operation. The pivot row is \(x_6\), the only basic variable with a negative value. The ratios of the non-basic variables with \(\bar a_{6j} < 0\) are

  \[ \frac{\bar c_{3}}{\bar a_{6,3}} = \frac{-\tfrac{1}{2}}{-\tfrac{1}{4}} = 2,\qquad \frac{\bar c_{5}}{\bar a_{6,5}} = \frac{-2}{-\tfrac{5}{2}} = \dfrac{4}{5}. \]

• The pivot column is \(x_5\), with \(s_m = \dfrac{4}{5}\), and the objective value becomes \(\bar z + s_m \, \bar b_{6} = \dfrac{29}{2} + \dfrac{4}{5} \cdot \left(-\dfrac{1}{4}\right) = \dfrac{143}{10}\). The new dictionary is primal and dual feasible, hence optimal:

\[\begin{equation*} \begin{cases} \begin{array}{rrrrrrr} {x_1} & {=} & {\dfrac{41}{10}} & {-} & {\dfrac{1}{10}}\, {x_3} & {+} & {\dfrac{2}{5}}\, {x_6} \\[2ex] {x_2} & {=} & {1} & & & {-} & {x_6} \\[2ex] {x_4} & {=} & {\dfrac{93}{5}} & {+} & {\dfrac{2}{5}}\, {x_3} & {+} & {\dfrac{62}{5}}\, {x_6} \\[2ex] {x_5} & {=} & {\dfrac{1}{10}} & {-} & {\dfrac{1}{10}}\, {x_3} & {+} & {\dfrac{2}{5}}\, {x_6} \\[2ex] {z} & {=} & {\dfrac{143}{10}} & {-} & {\dfrac{3}{10}}\, {x_3} & {-} & {\dfrac{4}{5}}\, {x_6} \end{array} \end{cases} \end{equation*}\]

• The solution \(\tilde{\vet x}(\LP_3) = (\tfrac{41}{10},1)\), with value \(\tfrac{143}{10}\), is the same that the down-branching child of node \(3\) gives: here the local cut works as a branching constraint, without creating a new node.

Example 8.4: a Gomory fractional cut at node 3

• The row of \(x_2\) of the dictionary of node \(3\) gives the Gomory fractional cut

\[ \dfrac{1}{4} \, x_3 + \dfrac{1}{2} \, x_5 \ge \dfrac{1}{4} \]

• It contains the slack variable \(x_5\) of the branching constraint \(x_1 \ge 4\), so its derivation uses this constraint and the algorithm treats it as a local cut.

• In the space of the original variables (\(x_3 = 45 - 10\,x_1 - 4\,x_2\), \(x_5 = x_1 - 4\), multiplied by \(4\)) it reads \(2\,x_1 + x_2 \le 9\). Enumerating the \(16\) integer feasible solutions we see that this inequality is valid for all of them.

• The algorithm cannot make this check at a node, so it keeps the cut local.

8.6 Practical aspects

8.6.1 Cut selection

• At each round many violated cuts can be available; adding all of them makes the LP problems large and slow to re-optimize. A branch-and-cut algorithm selects a subset.

• The efficacy of a cut \(\vet\alpha\T\vet x \le \beta\) at the fractional solution \(\tilde{\vet x}(\LP_k)\) is the Euclidean distance of \(\tilde{\vet x}(\LP_k)\) from the hyperplane \(\vet\alpha\T\vet x = \beta\):

  \[ \text{efficacy} = \frac{\vet\alpha\T\,\tilde{\vet x}(\LP_k) - \beta}{\|\vet\alpha\|_2}. \]

• Unlike the violation \(\vet\alpha\T\tilde{\vet x}(\LP_k) - \beta\), the efficacy does not change if the cut is multiplied by a positive constant. Selection rules combine efficacy with a measure of the parallelism of the cuts.

• For example, at \(\tilde{\vet x}(\LP_1) = (5,\tfrac{7}{2})\) of \(P10\) the cut \(3x_1 - x_2 \le 11\) has violation \(\frac{1}{2}\) and efficacy \(\frac{1}{2\sqrt{10}} \approx 0.158\), while the same cut multiplied by \(2\), \(6x_1 - 2x_2 \le 22\), has violation \(1\) and the same efficacy \(\frac{1}{\sqrt{40}} \approx 0.158\).

8.6.2 Which cuts

• Any family of valid inequalities with a separation procedure can be used: Gomory fractional cuts (for ILP problems with integer data), cover inequalities for the constraints \(\sum_j a_j x_j \le b\) with positive coefficients of a MIP problem with binary variables, and families that exploit the structure of a given model.

• Gomory fractional cuts come from the rows of the optimal dictionary, so they are always available. In floating-point arithmetic their coefficients are affected by rounding errors, and solvers discard the cuts with very large or very small coefficients.

8.6.3 Upper bound and gap

• As in the branch-and-bound algorithm, if the list \(L\) is not empty we have

  \[ z(\ILP) ~~\le~~ \UB ~=~ \max_{k \in L} \left\{~ \mathrm{UB}(\LP_k) ~\right\}, \]

  where \(z(\LP_k)\) is now the optimal value of the \(\LP_k\) problem after the cuts.

• Cuts decrease the values \(z(\LP_k)\) and, accordingly, the upper bound \(\UB\) and the optimality gap \(\frac{\UB - \LB}{|\LB|}\).

8.7 Typical mistakes

Warning

• Using a local cut outside its subtree. A cut derived with a branching constraint of node \(k\) is valid only in the subtree of node \(k\): in another branch it can remove an optimal solution.

• Treating a cut as global without a proof. A Gomory fractional cut generated at a node can be global by chance (Example 8.4); the algorithm keeps it local unless its derivation does not use branching constraints.

• Adding every violated cut. Too many cuts make the LP problems slow; a few effective cuts per round are better, and inactive cuts are removed.

• Believing that every cut reduces the tree. On \(P2\) the first three Gomory cuts leave the tree at \(4\) nodes (table of Section 8.4); the quality of the cuts matters.

• Choosing the cut with the largest efficacy as the strongest. Efficacy is measured at the current point only: a dominated cut can have a larger efficacy at that point.

• Forgetting that cuts decrease the bound, not the optimal value. The optimal value \(z(\ILP)\) never changes: only \(z(\LP_k)\) and the upper bound do.

8.8 In summary

In summary

• A branch-and-cut algorithm strengthens the LP problem of every node with cuts before branching.

• A global cut is valid for all the integer solutions; a local cut only for those of a subtree, and it is stored with its node.

• A cut-and-branch algorithm generates cuts only at the root; the cuts are then global.

• After a cut, the LP problem is re-optimized with the dual simplex algorithm from the previous dictionary.

• Cuts reduce the size of the tree, but only effective cuts do: on \(P10\), one Gomory cut reduces the tree from \(5\) to \(3\) LP problems, and two cuts to \(1\).

Dashboard of \(P10\). The lower and upper bounds on \(z(\ILP) = 28\) found in this chapter:

Stage	Lower bound	Upper bound	From
LP relaxation of \(P10\)	—	\(32\)	\(z(\LP) = 32\), \(\tilde{\vet x}(\LP) = (5,\tfrac{7}{2})\)
Branch-and-bound	\(28\)	\(28\)	\(5\) LP problems solved
After the first Gomory cut	—	\(31\)	\(z(\LP_1) = \tfrac{220}{7}\)
Cut-and-branch with one cut	\(28\)	\(28\)	\(3\) LP problems solved
After the second Gomory cut	\(28\)	\(28\)	\(\tilde{\vet x}(\LP_1) = (4,4)\) is integer, \(1\) LP problem solved

How MIP solvers combine these ideas is the topic of the chapter «MIP solvers».

---

Exercises on this chapter: Branch-and-cut