Column Generation and Branch and Price Decomposition

32 concepts31 papers1 proposal

In large-scale combinatorial optimization, algorithms frequently collide with a fundamental barrier: the exponential growth of decision variables. Whether scheduling observations on a telescope, routing a fleet of electric vehicles, or matching patients in a kidney exchange, the number of valid individual schedules, routes, or exchange chains grows astronomically with the size of the problem.

A monolithic Integer Linear Programming (ILP) solver attempts to evaluate all possible variables simultaneously, quickly exhausting computational memory. To bypass this bottleneck, researchers use Column Generation and Branch-and-Price algorithms. This paradigm breaks a massive optimization problem into smaller, interconnected pieces, generating only the variables that are mathematically proven to improve the solution.

The Core Mechanism: Master-Subproblem Decomposition

The foundational intuition behind column generation is that out of millions of potential variables (or "columns"), only a tiny fraction will actually feature in the optimal solution. Instead of starting with every possible column, the algorithm begins with a heavily restricted subset of variables.

This setup relies on a mathematical technique known as Dantzig-Wolfe decomposition, which splits the problem into two distinct components:

  1. The Restricted Master Problem (RMP): A global coordinator that selects the best combination of columns from the current pool to minimize or maximize an overall objective.
  2. The Pricing Subproblem: A local optimizer tasked with generating new columns that could potentially improve the RMP's current solution.

The RMP and the subproblem communicate via a continuous feedback loop driven by linear programming duality. When the RMP is solved to fractional optimality, it outputs dual prices (or shadow prices) for each global constraint. These dual prices represent the marginal value or "cost" of using a specific resource.

The pricing subproblem ingests these dual prices and searches the combinatorial space for a new column with a negative reduced cost (in a minimization problem). If the subproblem finds such a column, it is added to the RMP, and the loop repeats. If no columns with a negative reduced cost exist, the current solution is mathematically guaranteed to be optimal for the continuous relaxation of the problem.

As shown by Jendrik Seipp et al. in Dantzig-Wolfe Decomposition for Cost Partitioning, this iterative process allows systems to find optimal partitions by evaluating only a fraction of the total variable space, avoiding monolithic memory overhead.

Why It Works: Intuition of the Pricing Loop

To understand why this feedback loop is so effective, consider how it applies to real-world constraints. In radiation therapy scheduling, as explored by Sara Frimodig et al. in Radiation therapy patient scheduling using a column generation approach: an algorithmic framework and a single-institution study, the master problem ensures that overall clinical capacity is not exceeded, while individual subproblems generate feasible schedules for single patients.

If a particular machine becomes highly contested, the RMP assigns a high dual price to that time slot. The pricing subproblem receives this price and penalizes any new patient schedule that uses that slot. Consequently, the subproblem naturally shifts toward generating schedules that utilize under-allocated resources.

This mechanism allows column generation to scale across diverse domains:

Enforcing Integrality: Branch-and-Price

While column generation efficiently solves the linear programming relaxation of a problem, real-world decisions are binary: a ship either sails a route or it does not; an observation is either scheduled or omitted.

Standard branch-and-bound algorithms fail when combined directly with column generation. If a solver branches by fixing a specific column variable to zero, the pricing subproblem—unaware of this restriction—may simply regenerate that exact same column in the next iteration, trapping the solver in an infinite loop.

To resolve this, Branch-and-Price embeds column generation inside a specialized branch-and-bound tree. Instead of branching on the columns themselves, the algorithm branches on the underlying structural decisions within the subproblem.

For example, in maritime logistics, Erik Orm Hellsten demonstrates in A branch-and-price algorithm for solving the single-hub feeder network design problem that branching should occur on whether a specific vessel traverses a particular arc. This modifies the subproblem's topology (by removing or forcing an edge) rather than banning a final route, ensuring that subsequent column generation steps respect the branch conditions without destroying the subproblem's structure.

Because exploring a full branch-and-price tree can be computationally expensive, modern implementations rely on specialized heuristics to find high-quality integer solutions quickly:

By decoupling global coordination from local feasibility, column generation and branch-and-price transform intractable, exponentially large optimization problems into a sequence of manageable, targeted subproblems.

Key Foundational Work

A carrier’s optimal bid generation problem in combinatorial auctions for transportation procurement (2006) — contributed 1 concept elements to this direction.
Vehicle Routing and Staffing for Sedan Service (2006) — contributed 1 concept elements to this direction.
On the Relationship between Probabilistic Logic (1999) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_branch_and_price_algorithm_8d6388af,
  title = {branch-and-price algorithm},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/branch-and-price-algorithm/rdr_8d6388af01714330b462af446752e0af},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_branch_and_price_algorithm_8d6388af_v1,
  title = {branch-and-price algorithm},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/branch-and-price-algorithm/rdr_8d6388af01714330b462af446752e0af/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake