Proposition 2 — a strictly redundant column is never optimal for the ratio pricing problem (31)

Consider a set-partitioning master problem with rows $\{1,\dots,m\}$, a finite collection $\mathcal A$ of nonempty columns (subsets of the rows, with incidence vectors $\mathbf a \in \{0,1\}^m$) and costs $\mathbf c$. Let $(\mathcal A, \mathbf c)$ satisfy the subcolumn property ($c_r < c_s$ for all $r, s \in \mathcal A$ with $r \subsetneq s$), and let $\bar{\mathbf u} \in \mathbb R^m$ be an arbitrary vector of dual multipliers. If $\mathbf a_s \in \mathcal A$ is a strictly redundant column, i.e. there are $\lambda_r \ge 0$ with

then $\mathbf a_s$ is not an optimal solution of the ratio pricing problem

that is, it is not the case that the ratio of $\mathbf a_s$ is at most the ratio of every column of $\mathcal A$.

The result says that pricing by reduced cost per covered row, instead of by reduced cost alone (Dantzig's rule), never selects a column whose dual constraint is strictly implied by those of its subcolumns. The paper states the proposition and attributes the concept to Sol (1994); it gives no proof.

Formalization Note. The paper leaves the sign of $\lambda_r$ in (30) implicit; this statement reads it as $\lambda_r \ge 0$, the Farkas form of "the corresponding constraint is redundant for the dual problem" (with signed multipliers the proposition is false). The sums range over the columns of $\mathcal A$ that are proper subsets of $s$. The hypothesis $\emptyset \notin \mathcal A$ is the reading of the denominator $\mathbf 1^{\mathsf T}\mathbf a$ in (31): a set-partitioning column covers at least one row (Lean's division by $0$ would otherwise give the empty column ratio $0$). The multipliers $\bar{\mathbf u}$ are free, as the rows are equalities; no sign or optimality is assumed. "Cannot be an optimal solution" is stated literally as $\neg(\forall \mathbf a \in \mathcal A,\ \text{ratio}(\mathbf a_s) \le \text{ratio}(\mathbf a))$, which is equivalent to the existence of a column of $\mathcal A$ with strictly smaller ratio. The subcolumn property is the paper's hypothesis and is kept, although the conclusion may not need it.