Problem Statement

MIP

We consider the following generic mixed-integer programming model to explain Benders’ Decomposition. (The notation used is similar to [FSZ10].)

\[\begin{split}\begin{align} & \text{minimize} & & c^Tx + d^Ty \\ & \text{subject to} & & A x \leq b & & \\ &&& T x + Q y \leq r & & \\ &&& x \in \mathbb{Z}^n_+ & & \\ &&& y \in \mathbb{R}^m_+ & & \\ \end{align}\end{split}\]

The variable \(x\) is integer and the variable \(y\) is continuous. The matrix \(T\) may contain empty constraints but we assume that the matrix \(Q\) does not contain any empty constraint. So, the model can have constraints that only contain continuous variables.

Limitation

Benders’ Decomposition cannot be used if the model contains only integer variables. If the number of continuous variable is small compared to the number of integer variables then Benders’ Decomposition will very likely be inefficient.