Valid inequalities

Part 2 · Strengthening the formulation · Chapter 4 · Lecture notes, volume 1 (PDF) · Exercises: Valid inequalities · App: Valid inequalities and the convex hull

Prerequisites

• From this module, the chapter «Primal and dual bounds»: the LP relaxation, the rounded bound \(\lfloor z(\LP) \rfloor\), and bounds from non-negative multipliers of the constraints.

• From this module, the chapter «Ideal formulations»: formulations, the convex hull, and the comparison of formulations through their polyhedra.

Objectives

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

• define a valid inequality, and say when it cuts off a fractional point;

• derive a valid inequality from non-negative multipliers of the constraints by rounding down;

• improve a valid inequality until it touches a feasible integer point;

• measure the effect of a valid inequality on the optimal value of the LP relaxation and on the upper bound;

• explain why valid inequalities are the practical way to approach an ideal formulation.

Where we were

In the car example the ideal formulation gives the upper bound \(14\), equal to the lower bound, so it certifies that \((4,1)\) is optimal. But we found its four inequalities by looking at the convex hull, which is not possible in general. We now learn to derive such inequalities from the constraints.

4.1 Valid inequalities

Definition 4.1: of valid inequality

An inequality \(\sum_{j=1}^n \alpha_j \, x_j \le \beta\) is a valid inequality for an ILP problem with feasible region \(F\) if it is satisfied by all the points of \(F\).

Definition 4.2: cut-off point and tight valid inequality

Let \(\sum_{j=1}^n \alpha_j \, x_j \le \beta\) be a valid inequality for an ILP problem with feasible region \(F\).

• The inequality cuts off a point \(\vet x^* \in \R^n\) if \(\sum_{j=1}^n \alpha_j \, x^*_j > \beta\).

• The inequality is tight if at least one point of \(F\) satisfies it with equality.

• A valid inequality cuts off no point of \(F\), but it can cut off fractional points of the LP relaxation. The right-hand side of a tight inequality cannot be decreased without losing a feasible solution.

• Adding a valid inequality to the formulation does not change \(F\), and it shrinks the polyhedron \(P\). The new formulation is stronger, so its LP relaxation gives an upper bound that is not worse.

• A valid inequality is satisfied by a point of \(F\) if and only if it is satisfied by the convex hull, so it is valid for \(\mathrm{conv}(F)\). The inequalities of the ideal formulation are valid inequalities.

A valid inequality removes fractional points and never an integer feasible solution. Adding valid inequalities makes the formulation stronger and the upper bound better.

Example 4.1: valid inequalities of the car example

The inequalities \(x_1 \le 4\) and \(x_2 \le 3\) of the previous chapters are valid inequalities of the car example. They do not cut off the optimal solution \((\frac{7}{2},\frac{5}{2})\) of the LP relaxation, so they do not improve the upper bound \(15\).

4.2 Deriving valid inequalities by rounding

• The constraints are combined with non-negative multipliers, as for the dual bounds; since the variables are integer, the right-hand side of the combination can be rounded down.

Proposition 4.3: valid inequalities by rounding

Let \(\pi_1, \pi_2, \dots, \pi_m \ge 0\) be multipliers such that \(\sum_{i=1}^m \pi_i \, a_{ij} \ge \alpha_j\), with \(\alpha_j \in \Z\), for all \(j \in \{1,2,\dots,n\}\). Then the inequality

\[\begin{equation*} \label{rounding} \sum_{j=1}^n \alpha_j \, x_j ~\le~ \left\lfloor \sum_{i=1}^m \pi_i \, b_i \right\rfloor \tag{4.1} \end{equation*}\]

is valid for the ILP problem.

Proof

For every feasible solution, \(\sum_j \alpha_j \, x_j \le \sum_j \big( \sum_i \pi_i \, a_{ij} \big) x_j \le \sum_i \pi_i \, b_i\), by \(x_j \ge 0\) and by the constraints multiplied by \(\pi_i \ge 0\). The left-hand side is an integer, because \(\alpha_j\) and \(x_j\) are integer, so it is at most the integer part of the right-hand side. □

• The proposition needs all the variables to be integer and non-negative. With a continuous variable the left-hand side is not an integer, and the right-hand side cannot be rounded.

Example 4.2: rounding with multiplier \(\frac{1}{2}\)

In the car example, multiply the first constraint by \(\frac{1}{2}\): we get \(5\,x_1 + 2\,x_2 \le \frac{45}{2}\). Since the left-hand side is integer, we obtain the valid inequality

\[ 5\,x_1 + 2\,x_2 \le 22. \]

Multiplying the second constraint by \(\frac{1}{2}\) we get \(2\,x_1 + 7\,x_2 \le \frac{49}{2}\), hence

\[ 2\,x_1 + 7\,x_2 \le 24. \]

Both inequalities cut off the optimal solution \((\frac{7}{2},\frac{5}{2})\) of the LP relaxation: \(5 \cdot \frac{7}{2} + 2 \cdot \frac{5}{2} = \frac{45}{2} > 22\) and \(2 \cdot \frac{7}{2} + 7 \cdot \frac{5}{2} = \frac{49}{2} > 24\). The new LP relaxations give:

Added inequality	\(\tilde{\vet x}(\LP)\)	\(z(\LP)\)	\(\lfloor z(\LP) \rfloor\)
none	\((\frac{7}{2},\frac{5}{2})\)	\(\frac{31}{2}\)	\(15\)
\(5\,x_1 + 2\,x_2 \le 22\)	\((\frac{105}{31},\frac{157}{62})\)	\(\frac{472}{31}\)	\(15\)
\(2\,x_1 + 7\,x_2 \le 24\)	\((\frac{219}{62},\frac{75}{31})\)	\(\frac{957}{62}\)	\(15\)

The LP optimum moves, but the upper bound does not improve: \(\lfloor \frac{472}{31} \rfloor = \lfloor \frac{957}{62} \rfloor = 15\).

A valid inequality that cuts off the optimal LP solution does not always improve the upper bound. The choice of the multipliers matters: we look for inequalities that touch the integer points.

4.3 Improving a valid inequality

• Given the coefficients \(\alpha_j\), the strongest valid inequality has the smallest possible right-hand side, which is the maximum of \(\sum_j \alpha_j \, x_j\) over \(F\). We find it by lowering the right-hand side \(\beta\) of \(\eqref{rounding}\) until a feasible integer point reaches it.

Algorithm

• Input: An ILP problem in canonical maximization form with \(F \ne \emptyset\), and integer coefficients \(\alpha_1, \alpha_2, \dots, \alpha_n\).

• Output: A tight valid inequality \(\sum_{j=1}^n \alpha_j \, x_j \le \beta\).

• Step 0: Coarse bound

  Find multipliers \(\pi_i \ge 0\) with \(\sum_{i} \pi_i \, a_{ij} \ge \alpha_j\) for all \(j\), and set \(\beta \leftarrow \lfloor \sum_{i} \pi_i \, b_i \rfloor\).

• Step 1: Test the right-hand side

  If no feasible integer point satisfies \(\sum_{j} \alpha_j \, x_j = \beta\), set \(\beta \leftarrow \beta - 1\) and repeat Step 1.

• Step 2: Tight inequality

  A feasible integer point satisfies \(\sum_{j} \alpha_j \, x_j = \beta\), so \(\sum_{j} \alpha_j \, x_j \le \beta\) is valid and tight. STOP.

• In Step 0 the multipliers can be chosen freely: the better they are, the fewer repetitions of Step 1 are needed. In Step 1, for two variables, we substitute one variable using the equation and bound the other one with the constraints: if the bounds contradict each other, no point exists.

Example 4.3: the inequality \(x_1 + x_2 \le 5\)

We look for a valid inequality with \(\alpha = (1,1)\).

• Step 0. With the multipliers \((\frac{1}{14},\frac{1}{14})\) the sum of the constraints, divided by \(14\), is \(x_1 + \frac{9}{7}\,x_2 \le \frac{47}{7}\). The coefficients are at least \((1,1)\), so \(x_1 + x_2 \le \lfloor \frac{47}{7} \rfloor = 6\), and we set \(\beta = 6\).

• Step 1, \(\beta = 6\). Let \(x_1 + x_2 = 6\), so \(x_2 = 6 - x_1\). The first constraint becomes \(6\,x_1 + 24 \le 45\), that is \(x_1 \le \frac{7}{2}\), hence \(x_1 \le 3\). The second becomes \(84 - 10\,x_1 \le 49\), that is \(x_1 \ge \frac{7}{2}\), hence \(x_1 \ge 4\). The bounds contradict each other: no feasible point has \(x_1 + x_2 = 6\), and we set \(\beta = 5\).

• Step 1, \(\beta = 5\). Let \(x_2 = 5 - x_1\). The constraints become \(x_1 \le \frac{25}{6}\), hence \(x_1 \le 4\), and \(x_1 \ge \frac{21}{10}\), hence \(x_1 \ge 3\). There is no contradiction, and the points \((3,2)\) and \((4,1)\) are feasible with \(x_1 + x_2 = 5\).

• Step 2. The inequality \(x_1 + x_2 \le 5\) is valid and tight.

It cuts off \((\frac{7}{2},\frac{5}{2})\) (the sum is \(6\)). The new LP relaxation has the optimal solution \((\frac{25}{6},\frac{5}{6})\) with \(z(\LP) = \frac{85}{6}\), so the upper bound is \(\lfloor \frac{85}{6} \rfloor = 14\).

The valid inequality \(x_1 + x_2 \le 5\) (green) cuts off the gray triangle, which contains no integer point, and the optimal solution of the previous LP relaxation. The new optimal solution is \((\frac{25}{6},\frac{5}{6})\) (blue), with \(z = \frac{85}{6}\) (dashed line).

Example 4.4: the inequality \(x_1 + 2\,x_2 \le 7\)

We look for a valid inequality with \(\alpha = (1,2)\).

• Step 0. With the multipliers \((\frac{3}{62},\frac{4}{31})\) the combination of the constraints is \(x_1 + 2\,x_2 \le \frac{17}{2}\), because \(\frac{3 \cdot 10}{62} + \frac{4 \cdot 4}{31} = 1\), \(\frac{3 \cdot 4}{62} + \frac{4 \cdot 14}{31} = 2\) and \(\frac{3 \cdot 45}{62} + \frac{4 \cdot 49}{31} = \frac{17}{2}\). Hence \(x_1 + 2\,x_2 \le \lfloor \frac{17}{2} \rfloor = 8\), and we set \(\beta = 8\).

• Step 1, \(\beta = 8\). Let \(x_1 = 8 - 2\,x_2\). The first constraint becomes \(80 - 16\,x_2 \le 45\), hence \(x_2 \ge 3\); the second becomes \(32 + 6\,x_2 \le 49\), hence \(x_2 \le 2\). They contradict each other, and we set \(\beta = 7\).

• Step 1, \(\beta = 7\). Let \(x_1 = 7 - 2\,x_2\): the constraints become \(70 - 16\,x_2 \le 45\), hence \(x_2 \ge 2\), and \(28 + 6\,x_2 \le 49\), hence \(x_2 \le 3\). The points \((3,2)\) and \((1,3)\) are feasible with \(x_1 + 2\,x_2 = 7\).

• Step 2. The inequality \(x_1 + 2\,x_2 \le 7\) is valid and tight.

The new LP relaxation has the optimal solution \((\frac{31}{8},\frac{25}{16})\) with \(z(\LP) = \frac{59}{4}\), so the upper bound is \(\lfloor \frac{59}{4} \rfloor = 14\).

The valid inequality \(x_1 + 2\,x_2 \le 7\) (green) cuts off the gray triangle, which contains no integer point. The new optimal solution is \((\frac{31}{8},\frac{25}{16})\) (blue), with \(z = \frac{59}{4}\) (dashed line).

With the valid inequality \(x_1 + x_2 \le 5\), or with \(x_1 + 2\,x_2 \le 7\), the upper bound drops from \(15\) to \(14\). It equals the lower bound given by \((4,1)\): the solution \((4,1)\) is certified optimal, and the gap is zero.

• The two inequalities, together with \(x_1 \le 4\) and \(x_2 \le 3\), are exactly the four inequalities of the ideal formulation of the previous chapter. For the car example we have reached the convex hull with valid inequalities derived from the constraints.

4.4 Families of valid inequalities and cuts

• With two variables the directions \(\alpha\) are chosen on the picture. In general, valid inequalities come from two sources.

• Families of inequalities for specific structures of the constraints, such as the cover inequalities of a constraint with positive coefficients of a binary problem (next chapter).

• The rounding of this chapter, applied systematically to the rows of the optimal dictionary of the LP relaxation: the Gomory fractional cuts of the cutting plane algorithm, and then the branch-and-cut algorithm.

4.5 Typical mistakes

Warning

• Rounding when a variable is continuous. The rounding of \(\eqref{rounding}\) needs integer variables and integer coefficients \(\alpha_j\).

• Rounding up instead of down. The right-hand side is rounded down. Rounding up gives an inequality that is not valid, and it can remove integer solutions.

• Believing that every valid inequality improves the bound. The inequalities \(5\,x_1 + 2\,x_2 \le 22\) and \(2\,x_1 + 7\,x_2 \le 24\) cut off the LP optimum, but leave the bound at \(15\).

• Using multipliers that are not large enough. The combined coefficients must be at least \(\alpha_j\) for every \(j\), and the multipliers must be non-negative.

• Stopping at a coarse right-hand side. The inequality \(x_1 + x_2 \le 6\) is valid, but it does not cut off the LP optimum of the car example (its sum is \(6\)); the tight inequality \(x_1 + x_2 \le 5\) does.

4.6 In summary

In summary

• A valid inequality is satisfied by all the feasible integer solutions; it can cut off fractional points of the LP relaxation, and it makes the formulation stronger.

• Non-negative multipliers of the constraints, with the right-hand side rounded down, give valid inequalities for ILP problems.

• Lowering the right-hand side until an integer point touches the line gives a tight inequality.

• A valid inequality helps only if it cuts off the LP optimum and improves the rounded bound.

• In the car example, \(x_1 + x_2 \le 5\) or \(x_1 + 2\,x_2 \le 7\) lowers the upper bound from \(15\) to \(14\), and certifies that \((4,1)\) is optimal.

Dashboard of the car example. The bounds on \(z(\ILP)\) found so far in this module:

Chapter	Lower bound	Upper bound	From
Primal and dual bounds	\(14\)	\(15\)	heuristic solution \((4, 1)\), and \(\lfloor z(\LP) \rfloor\) with \(z(\LP) = \tfrac{31}{2}\)
Ideal formulations	\(14\)	\(14\)	ideal formulation, optimal vertex \((4,1)\)
Valid inequalities	\(14\)	\(14\)	\(x_1 + x_2 \le 5\) gives \(z(\LP) = \tfrac{85}{6}\)

---

Exercises on this chapter: Valid inequalities

Interactive lab

The ideas of the chapter, hands on: move the sliders and drag the points. Each app also opens full page in the interactive lab: Valid inequalities and the convex hull.