Takeaway

Benders splits a hard problem into a master over complicating variables and subproblems over the rest; iteratively add feasibility/optimality cuts from subproblem duals.

The problem (before → after)

  • Before: Monolithic MILPs/LPs with block structure are too big to solve directly.
  • After: Exploit separability to solve subproblems in parallel and guide the master with informative cuts.

Mental model first

It’s like planning a road trip (master: cities to visit) and then checking feasibility on each leg (subproblems: route details). If a leg is impossible, add a rule to avoid that plan next time; if feasible, refine with cost information.

Just-in-time concepts

  • Complicating variables; master problem; subproblems.
  • Dual subproblem yields Benders cuts.
  • Convergence via cut generation and bounds.

First-pass solution

Fix master vars; solve subproblems; if infeasible, add feasibility cut; else add optimality cut; repeat until gap closes.

Iterative refinement

  1. Generalized Benders handles nonlinear structures.
  2. Acceleration: cut selection, Pareto-optimal cuts, stabilization.
  3. Parallel subproblem solves for speed.

Principles, not prescriptions

  • Align decomposition with block structure for strong cuts.
  • Stabilize master to avoid oscillations.

Common pitfalls

  • Weak or too many cuts slow convergence.
  • Poor initial master guesses cause long warm-up.

Connections and contrasts

  • See also: [/blog/branch-and-bound], [/blog/convex-optimization], [/blog/optimal-transport].

Quick checks

  1. Why dual subproblems? — Dual variables generate informative cuts.
  2. When to use? — Block-separable substructures with complicating link variables.
  3. How to parallelize? — Solve subproblems per block simultaneously.

Further reading

  • Benders (1962); modern MIP literature