3
$\begingroup$

I am trying to understand Benders Decomposition method. I am reading this book Decomposition techniques in mathematical programming by A Conejo, E Castillo, R Minguez. The book provides an example of Benders decomposition (pages 118-120). The problem is given as:

$$ \begin{align} \text{minimise} \hspace{0.5cm} &z = -y - x/4 \\ \text{s.t.} \hspace{0.5cm} & y -x \leq 5 \\ & y -\frac{1}{2}x \leq \frac{15}{2} \\ & y + \frac{1}{2}x \leq \frac{35}{2} \\ & -y+x \leq 10 \\ & 0 \leq x \leq 16 \\ & y \geq 0 \end{align} $$

$x$ and $y$ are (continuous) variables.

For decomposition, the Master problem is defined as

$$ \begin{align} \text{minimise} \hspace{0.5cm} & -\frac{1}{4}x + \alpha \\ \text{s.t.} \hspace{0.5cm} & 0 \leq x \leq 16 \\ & -25 \leq \alpha \end{align} $$

The sub problem is given as:

$$ \begin{align} \text{minimise} \hspace{0.5cm} & z = -y \\ \text{s.t.} \hspace{0.5cm} & y - x \leq 5 \\ & y -\frac{1}{2}x \leq \frac{15}{2} \\ & y + \frac{1}{2}x \leq \frac{35}{2} \\ & -y+x \leq 10 \\ & 0 \leq x \leq 16 \\ & y \geq 0 \\ & x = 16 \end{align} $$

I don’t understand how this bound or constraint of -25 on $\alpha$ in the Master problem is determined and the constraint of $x=16$ in the sub problem. Can someone please explain?

$\endgroup$

1 Answer 1

7
$\begingroup$

$\alpha$ is a surrogate for $-y$, so the negative of any valid upper bound on $y$ is a valid lower bound on $\alpha$. You need such a bound since otherwise the master problem would be unbounded (pick a feasible $x$ and let $\alpha \rightarrow -\infty$). Why they picked -25 I can't say. Looking at the second constraint of the original problem and setting $x$ to its upper limit of $16$, you get $y\le 15.5$, so $\alpha \ge -15.5$ would be valid (and a bit tighter, not that it matters). I suspect they just picked -25 because it's valid and aesthetically pleasing in some way ... or maybe because they knew that, being smaller than $-y$ can ever get, it would trigger an optimality cut (for demonstration purposes).

As for the $x=16$ constraint, the idea of Benders is to solve the master (getting $x^*$ and $\alpha^*$), pass them to the subproblem as parameter values, and solve for $y$. If the subproblem is infeasible, you get a feasibility cut. If the subproblem is feasible but the optimal value $y^*$ of $y$ does not satisfy $-y^*\le \alpha^*$, you get an optimality cut. If neither of those problems arises, you have a winner. When you solve the initial master, you get $x^* = 16, \alpha^* = -25$. Rather than substitute 16 for $x$ in the subproblem, the authors apparently chose to add a constraint that sets $x$ equal to 16, which has the same effect. I will say that is more common to write the subproblem as if $x$ were a parameter (omitting $0\le x \le 16$ since $x$ is not a variable in the subproblem).

$\endgroup$
2
  • $\begingroup$ Thank you. I was not sure why there was no explanation in the book for -25, so your reasoning makes sense to me. One thing which is still confusing me is that the duals are not being used in the example. In step 1, the subproblem is solved which gives (x,y)= (16,19/2). In Step 2: upper bound and lower bound of the objective function are determined as: $$-\frac{1}{4}x - y = -\frac{1}{4}*16 - \frac{19}{2} = -\frac{27}{2}$$ and $$-\frac{1}{4}x + \alpha = -\frac{1}{4}*16 - 25 = -29 $$ $\endgroup$
    – Jonn
    Mar 27, 2022 at 0:30
  • $\begingroup$ Both those statements are correct. Neither is a Benders cut. Unfortunately, I'm not familiar with the book, so I can't say anything further. $\endgroup$
    – prubin
    Mar 27, 2022 at 15:02

Your Answer

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

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