Benders Decomposition for Fixed Charge Transportation Problem

Question

I am trying to write down the steps in Benders decomposition for the Fixed Charge Transportation Problem and was hoping someone could confirm/deny whether my understanding of it is correct. The original problem is $$ \newcommand{\mc}[1]{\mathcal{#1}} \begin{align*} \min~&\sum_{i\in \mc{I}}\sum_{j\in \mc{J}}c_{ij}x_{ij}+\sum_{i\in \mc{I}}\sum_{j\in \mc{J}}f_{ij}y_{ij}&\\ \text{s.t.}~&\sum_{j\in \mc{J}}x_{ij} \leq S_i& i\in \mc{I}\\ &\sum_{i\in \mc{I}}x_{ij} \geq D_j& j\in \mc{J}\\ &x_{ij}\leq u_{ij}y_{ij}& i\in\mc{I}, j\in \mc{J}\\ &y_{ij}\in\{0,1\},x_{ij}\geq 0& i\in \mc{I}, j\in\mc{J}. \end{align*} $$ with $u_{ij}=\min(S_i,D_j)$

Now, the $y$ variables are complicating, thus the master problem becomes $$ \begin{align} \min &\sum_{i\in\mathcal{I}}\sum_{j\in\mathcal{J}}f_{ij}y_{ij} + \alpha\\ &y_{i,j}\in \{0,1\}\hspace{25pt} i=1,2,...,I,j=1,2,...,J\\ &\alpha \geq 0 \end{align} $$

With the subproblem being $$ \begin{align} \alpha(y) = &\min \sum_{i\in \mc{I}}\sum_{j\in \mc{J}}c_{ij}x_{ij}\\ &\sum_{j\in \mc{J}}x_{ij} \leq S_i \hspace{25pt} (\tau_i)& i\in \mc{I}\\ &\sum_{i\in \mc{I}}x_{ij} \geq D_j \hspace{25pt} (\phi_j)& j\in \mc{J}\\ &x_{ij}\leq u_{ij}y_{ij} \hspace{25pt} (\psi_{ij})& i\in\mc{I}, j\in \mc{J}\\ &x_{ij}\geq 0& i\in \mc{I}, j\in\mc{J} \end{align} $$

Where I have put in parentheses the dual variables to the constraints. Is it then correct that if the subproblem is infeasible we will add a cut to the master problem that is

$$ \begin{align} \sum_{i\in\mathcal{I}}\tau_iS_i + \sum_{j\in\mathcal{J}}\phi_jD_j + \sum_{i\in\mathcal{i}}\sum_{j\in\mathcal{J}}\psi_{ij}u_{ij}y_{ij}\leq0 \end{align} $$

and if it feasible but the solution is not optimal in the original problem, then an optimality cut will be added: $$ \begin{align} \sum_{i\in\mathcal{I}}\tau_iS_i + \sum_{j\in\mathcal{J}}\phi_jD_j + \sum_{i\in\mathcal{i}}\sum_{j\in\mathcal{J}}\psi_{ij}u_{ij}y_{ij}\leq\alpha \end{align} $$

Am I understanding that right?

Answer 1

Yes, this looks correct. For comparison, check out Erwin Kalvelagen's Benders Decomposition with GAMS, which uses an equality-constrained version of this fixed charge transportation problem for illustration. Note that the equivalent dual LP is solved instead. Also, he provides two sets of valid constraints on $y$ that you can include a priori to strengthen the master problem: \begin{align} \sum_i S_i y_{ij} &\ge D_j &&\text{for all $j$} \tag1\label1\\ \sum_j D_j y_{ij} &\ge S_i &&\text{for all $i$} \tag2\label2 \end{align} Note that \eqref{2} assumes $\sum_i S_i = \sum_j D_j$, so omit \eqref{2} if that assumption is violated.