InteractiveMap of Operations Research
Back to Optimization Core
MethodAdvanced02.10
Optimization Core

Decomposition Methods

Split large models into pieces solvers can actually handle.

Overview

Decomposition Methods focuses on split large models into pieces solvers can actually handle. In the map of OR, it connects Benders, Column generation, Dantzig-Wolfe to decisions that must be modeled, solved, explained, and revised as evidence changes.

Benders, Dantzig-Wolfe, column generation, Lagrangian relaxation, and ADMM exploit structure across scenarios, networks, customers, and time periods. The practical use case is clearest in Crew scheduling, Unit commitment, Stochastic programs, Vehicle routing, where the method helps turn constraints and tradeoffs into a decision artifact someone can inspect.

Core ideas

Benders

Separates master decisions from subproblem evaluations when complicating variables create structure.

Column generation

Generates useful variables only when the pricing problem says they can improve the solution.

Dantzig-Wolfe

Dantzig-Wolfe is a core checkpoint for Decomposition Methods: define it concretely, attach units or rules where possible, and test whether stakeholders interpret it the same way.

Lagrangian relaxation

Lagrangian relaxation is a core checkpoint for Decomposition Methods: define it concretely, attach units or rules where possible, and test whether stakeholders interpret it the same way.

ADMM

ADMM is a core checkpoint for Decomposition Methods: define it concretely, attach units or rules where possible, and test whether stakeholders interpret it the same way.

How to use it

  1. 1Start with Crew scheduling: write the decision, time horizon, actors, and objective in operational language.
  2. 2Translate the problem into Benders, Column generation, and Dantzig-Wolfe; define units and data sources for each one.
  3. 3Build a small instance of Decomposition Methods that can be solved or simulated by hand inspection before using full production data.
  4. 4Compare the recommendation against a baseline policy, not just against mathematical optimality.
  5. 5Document assumptions, sensitivity results, and the conditions under which the recommendation should be revisited.

Applications

Crew schedulingUnit commitmentStochastic programsVehicle routing
  • Crew scheduling: compare feasible policies, quantify the operating tradeoffs, and make the assumptions behind the recommendation visible.
  • Unit commitment: compare feasible policies, quantify the operating tradeoffs, and make the assumptions behind the recommendation visible.
  • Stochastic programs: compare feasible policies, quantify the operating tradeoffs, and make the assumptions behind the recommendation visible.
  • Vehicle routing: compare feasible policies, quantify the operating tradeoffs, and make the assumptions behind the recommendation visible.

Common pitfalls

  • Applying Decomposition Methods because the label sounds appropriate while leaving the actual decision boundary vague.
  • Treating Benders as a technical detail instead of a modeling choice that affects the recommendation.
  • Reporting one answer without showing sensitivity to demand, capacity, costs, or behavioral assumptions.
  • Ignoring implementation details such as data quality, explainability, ownership, and how users will override bad recommendations.

Resources