What is a Valid Inequality?

Suppose we have a set $S \subseteq \mathbb{R}^n$ — for example, the set of feasible solutions to an integer program. We frequently want to characterize $S$ using linear inequalities.

An inequality $\pi^T x \leq \pi_0$, with coefficient vector $\pi \in \mathbb{R}^n$ and right-hand side $\pi_0 \in \mathbb{R}$, is valid for $S$ if every point of $S$ satisfies it:

$$\pi^T x \leq \pi_0 \quad \text{for all } x \in S.$$

Equivalently, the inequality is valid for $S$ if and only if

$$\max_{x \in S} \pi^T x \leq \pi_0.$$

For example, take $S = \{(1,0),\, (0,1),\, (2,1),\, (1,3)\}$. Is the inequality $x_1 + x_2 \leq 4$ valid for $S$? Evaluating $x_1 + x_2$ at each point gives $1,\, 1,\, 3,\, 4$. The maximum is $4$, and $4 \leq 4$, so the inequality is valid for $S$.

If instead we asked about $x_1 + x_2 \leq 3$, the point $(1,3)$ gives $1 + 3 = 4 > 3$, so this second inequality would fail to be valid.