Benders decomposition

From Glossary

Jump to: navigation, search

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

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

Generalized Benders decomposition considers the following mathematical program:

\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

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.

Personal tools