Recognizing When Column Generation is the Right Tool

Auditing a multi-commodity flow / time-expanded model to decide whether column generation is the appropriate solution method, based on structural signals (exponential variable count, tractable pricing) and counter-signals (small instances, intractable pricing, alternative decompositions).

Step 1 of 157%

Tutorial

The Two-Condition Test for Column Generation

A linear (or mixed-integer) program is a good candidate for column generation (CG) when both of the following structural conditions hold.

Condition 1 — Many variables, most zero at optimum. The formulation has so many variables that we cannot (or do not want to) enumerate them, but only a small subset is active at an optimal solution.

Condition 2 — Tractable pricing subproblem. Finding a non-basic variable with negative reduced cost can be solved efficiently by exploiting structure (typically a shortest path, knapsack, or other combinatorial subroutine).

Both must hold. Many variables alone does not justify CG if pricing is intractable. Conversely, a tractable pricing oracle is irrelevant if the formulation is already compact.

For a path-based multi-commodity flow (MCF) on a time-expanded graph with $K$ commodities, $|V|$ nodes, and $T$ time periods, the number of feasible space-time paths grows combinatorially in $T$ and $|V|$ . Letting $\pi_a \le 0$ be the duals of the coupling arc-capacity constraints and $\mu_k$ the dual of commodity $k$ 's demand constraint, the reduced cost of a candidate path $p$ for commodity $k$ is

\bar c_p \;=\; \sum_{a \in p}\big(c_a^k - \pi_a\big) \;-\; \mu_k.

Pricing reduces to a shortest-path search on the time-expanded DAG with reduced arc weights $c_a^k - \pi_a$ — polynomial per commodity. Both conditions are met, so CG fits.

The practical job of an auditor is to check these conditions before deciding that CG is the right tool.