Skip to main content

Worked Examples

Self-contained examples of Dantzig-Wolfe Decomposition in action — from classical cutting stock to network flows and crew scheduling.

  • Crew Scheduling

    Scheduling

    Airline crew scheduling formulated as set partitioning. Dantzig-Wolfe Decomposition generates crew pairings for each base via column generation, making a massive integer program tractable.

    Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46(3), 316–329.

  • Cutting Stock Problem

    Cutting Stock

    A classic application of Dantzig-Wolfe Decomposition where the pricing sub-problem is a knapsack problem and column generation produces optimal cutting patterns.

    Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849–859.

  • Multi-Commodity Network Flow

    Network Flow

    Network structure gives a natural block-angular LP. Dantzig-Wolfe Decomposition exploits commodity-level independence to decompose into per-commodity shortest-path sub-problems.

    Ford, L. R., & Fulkerson, D. R. (1958). A suggested computation for maximal multi-commodity network flows. Management Science, 5(1), 97–101.