# Benders decomposition

This decomposition separates complicating variables. The (original) semi-linear model is:

$LaTeX: \max \{ c^Tx + F(y) : x \in X, \; y \in Y, \; Ax + G(y) \le b \}.$

Generalized Benders decomposition considers the following mathematical program:

$LaTeX: \max \{ f(x, y) : g(x, y) \le 0, \; h(x, y) = 0, \; x \in X, \; y \in Y \}.$

Suppose this is not a convex program, but that with each fixed $LaTeX: y \in Y$, the remaining mathematical program (with $LaTeX: x$ being the only variable) is convex. The idea is to consider

$LaTeX: v(y) = \sup \{ f(x, y) : g(x, y) \le 0, \; h(x, y) = 0, \; x \in X \},$

and solve $LaTeX: \max \{v(y) : y \in Y\}$, with evaluations of $LaTeX: v$ requiring the solution to the convex program.