3
$\begingroup$

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?

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.