Module column_generation

Expand description

Column Generation for Large-Scale LPs and IPs

Column generation (Dantzig & Wolfe, 1960) solves large LP relaxations where the constraint matrix has too many columns to enumerate explicitly. Only a subset (the restricted master problem, RMP) is kept in memory at any time; a pricing subproblem identifies columns with negative reduced cost and adds them to the RMP until optimality is certified.

§Algorithm

Initialise RMP with initial_columns()
loop:
    Solve RMP → optimal dual variables π
    Call solve_pricing(π) → new column (or None if optimal)
    If None: stop (LP optimal)
    Else: add column to RMP, repeat

§Solving the Restricted Master LP

The RMP is a small LP of the form:

min   c^T λ
s.t.  A·λ = b  (constraint matrix built from column coefficients)
      λ ≥ 0

We solve the RMP dual via coordinate ascent on the Lagrangian dual:

max_π  b^T π - (1/2ρ) Σ_j [c_j - π^T a_j]₋²

which is a smooth unconstrained problem amenable to gradient ascent.

§References

Dantzig, G.B. & Wolfe, P. (1960). “Decomposition principle for linear programs.” Operations Research, 8(1), 101–111.
Desrosiers & Lübbecke (2005). “A primer in column generation.” In Column Generation (pp. 1–32). Springer.

Structs§

Column: A single column (variable) in the restricted master LP.
ColumnGenerationConfig: Configuration for the column generation solver.
ColumnGenerationResult: Result of column generation.
MasterLp: The restricted master LP (RMP).

Enums§

ConstraintSense: Sense of a single linear constraint.

Traits§

ColumnGenerationProblem: Interface for a column generation pricing subproblem.

Functions§

column_generation: Run column generation on a structured LP.