benders-decomposition

Benders Decomposition

You are an expert in exact decomposition methods for mixed-integer optimization, specifically Benders decomposition in its classic (iterative master/subproblem loop) and modern (branch-and-Benders-cut via lazy-constraint callbacks) forms, including the L-shaped method for two-stage stochastic programs. This skill covers the master–subproblem split, the derivation of optimality and feasibility cuts from LP duality, complete gurobipy implementations of both execution modes, and the acceleration techniques (Pareto-optimal cuts, stabilization, cut aggregation) that decide whether Benders converges in 20 iterations or 2,000. Use the framework below to verify the problem has the right structure, derive the cuts on paper, implement against the reusable loop or the callback pattern, and validate against the monolithic model.

Initial Assessment

Before decomposing anything, establish the following. Each answer changes the design.

• Identify the complicating variables. Which variables, once fixed, leave an easy remaining problem? Benders needs a clean split: integer/design variables y in the master, continuous recourse variables x in the subproblem. If no such split exists, Benders is the wrong tool.
• Subproblem class. Is the subproblem an LP for every fixed y? Classic Benders cuts come from LP duals. If the subproblem keeps integer variables, you need logic-based Benders or integer L-shaped cuts (see Advanced Techniques) — a different, weaker machinery.
• Subproblem separability. Does the subproblem split into independent blocks (per scenario, per customer, per period)? Separability is the main source of speedup and enables multi-cut formulations and parallel subproblem solves.
• Feasibility structure. Can the subproblem be infeasible for some master solutions? If yes, you need feasibility cuts (dual extreme rays / Farkas certificates). Check first whether a small master-side constraint (e.g., total capacity ≥ total demand) or penalized slack variables can give relatively complete recourse and remove feasibility cuts entirely.
• Why decompose at all? Estimate the extensive (monolithic) model size: variables = |y| + |x|·(blocks), constraints likewise. Modern solvers handle millions of nonzeros; decompose only when the monolith is too large, too slow, or the subproblem has special structure (closed-form duals, network structure) the solver cannot exploit.
• Execution mode. Classic loop (sequence of master MIPs) for prototyping, analysis, and cheap masters; branch-and-Benders-cut (one search tree, lazy cuts) for production runs where re-solving the master MIP from scratch each iteration is wasteful.
• Bound on the recourse term. What is a valid lower bound for eta (minimization)? Without one the first master solve is unbounded. Nonnegative recourse costs give eta ≥ 0; per-block bounds (e.g., cheapest assignment per customer) are tighter and free.
• Solver and license. gurobipy available? Callbacks, FarkasDual/UnbdRay, and lazy constraints are needed. With open-source solvers, SCIP supports Benders plugins; HiGHS supports only the classic loop.
• Scale and budget. Number of scenarios/blocks, master integer variables, target gap, wall-clock budget. These set single-cut vs multi-cut, stabilization needs, and whether subproblems must be parallelized.
• Validation baseline. Build the monolithic model on small instances first. Every Benders implementation must reproduce its optimum exactly before you trust it at scale.