DantzigWolfe

Dantzig-Wolfe decomposition is an optimization technique used to solve large-scale linear programming problems that exhibit a block-angular structure. It is named after George B. Dantzig and Philip Wolfe, who introduced the approach in the 1960s. The method is designed for problems where decisions can be partitioned into a set of subproblems connected by a smaller set of linking constraints.

In its typical form, the decision variables are divided into a master problem and several subproblems. Each subproblem has its own set of variables and constraints, and the subproblems generate feasible columns (patterns or extreme points) that can be combined in the master problem to meet the linking constraints. The master problem coordinates the usage of these columns by selecting a combination that minimizes the overall objective, while the subproblems, given the dual prices from the master, search for new columns with negative reduced cost to improve the solution.

A key feature of Dantzig-Wolfe is column generation: starting from a small set of columns, the algorithm iteratively solves the master problem, then solves pricing subproblems to identify new columns to add. The process repeats until no column with a negative reduced cost remains, yielding a bound and a feasible solution for the original problem.

Applications of Dantzig-Wolfe include cutting stock, set partitioning, vehicle routing, crew scheduling, and facility location. It is often combined with branch-and-price to handle integer decisions, producing exact solutions for large, structured problems where standard formulations are impractical.