benders-decompositionlisted

When the user wants to solve a structured MILP or two-stage stochastic program by Benders decomposition — splitting it into an integer master and LP subproblems, deriving optimality and feasibility cuts from subproblem duals, and implementing either the classic iterative loop or branch-and-Benders-cut with lazy-constraint callbacks in Gurobi. Also use when the user mentions "Benders decomposition," "Benders cuts," "L-shaped method," "feasibility cut," "optimality cut," "master problem," or when fixing a few complicating variables leaves an easy or separable subproblem. For scenario generation and SAA, see stochastic-optimization; for callback mechanics and parameters, see gurobi-advanced-features.
hajibabaie/combinatorial-optimization-skills · ★ 0 · AI & Automation · score 72

Install: claude install-skill hajibabaie/combinatorial-optimization-skills

# 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, weak