I want to apply Benders Decomposition to a kind of network design problem with nonlinear constraints on flow variables.

If some binary variables from the master are fixed (selecting arcs, resulting in a tree topology) there is a unique solution for the flow variables, so these are implicitely fixed. When interpreting these variables as constants, the resulting problem is an LP, so I was hoping that I can apply classical Benders Decomposition. However, the master variables occur as variable upper bounds on the flow variables and I fear that these inequalities would be needed to build the Benders cut.

Here's an abstract version of my model with the fixed master variables \(y\): \[ \min_{x, f, p} \sum_{a \in A} c_a x_a \] \[ \sum_{uv \in A} f_{uv} - \sum_{vw \in A} f_{vw} = d_v \] \[ M(1-y_{uv}) + p_u - p_v \ge f_{uv}^2 x_{uv} \] \[ 0 \le L^x_a \le x_a \le U^x_a \] \[ 0 \le f_a \le U^f_a y_a \] \[ L^p_v \le p_v \le U^p_v \]

So, given that \(y\) is suitably fixed, then \(f\) is uniquely determined. But does this mean that I can just consider \(f\) as constant coefficients for the purpose of solvin the (dual) LP?

asked 07 May '15, 06:51

rschwarz's gravatar image

accept rate: 21%

edited 07 May '15, 10:40

To clarify my concern, here's how I would write the dual LP (removing all \(f_a\) that are fixed to 0 because \(y_a = 0\), and all redundant, never-binding constraints): \[ \max_{\lambda} \quad \sum_a 0 \lambda_a + \sum_a L^x_a \lambda^L_a - \sum_a U^x_a \lambda^U_a + \sum_v L^p_v \lambda^L_v - \sum_v U^p_v \lambda^U_v \] \[ -f_a^2 \lambda_a + \lambda^L_a - \lambda^U_a \le c_a \] \[ \sum_{uv} \lambda_{uv} - \sum_{vw} \lambda_{vw} + \lambda^L_v - \lambda^U_v \le 0 \] \[ \lambda_a, \lambda^L_a, \lambda^U_a, \lambda^L_v, \lambda^U_v \ge 0 \]

(07 May '15, 10:36) rschwarz

If fixing \(y\) implicitly fixes \(f\), then you can consider \( (y, f) \) to be the proposed solution to the master problem and fix both in the subproblem (whether primal or dual).


answered 07 May '15, 15:41

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

Thanks for the answer!

If I consider \(f\) to be fixed from the master problem, then the \(f\) variables may also be present (nonlinearly) in the Benders cut, right?

I'd like to get a cut using only the binary variables \(y\) if possible. I could always weaken the cut by substituting \(L^f_a y_a\) for \(f_a\), but then I don't know whether the cut will be effective anymore...

(07 May '15, 15:56) rschwarz

Also, even if I consider \(f\) to be a master variable and therefore fixed in the subproblem, it still occurs as a coefficient \(f^2\) in the dual LP. In my understanding of Benders Decomposition, the fixed master variables should only be present in the objective of the dual LP, so that the extreme points and rays can be determined indepedently from the master variables. Unfortunately, my constraints are not separable w.r.t. \(x\) and \(f\).

(07 May '15, 17:13) rschwarz

The product \(f^2_{uv}x_{uv}\) is definitely a problem. Sorry, I didn't notice that before. (I'm used to \(x\) being the master variable and \(y\) the subproblem variable. It gets habit-forming.) Benders conventionally involves a subproblem where the effect of the (fixed) master variables is on the RHS of the constraints, not on the coefficients of subproblem variables (whether they be objective coefficients or constraint coefficients). I don't know a way to apply Benders to your case.

(07 May '15, 18:05) Paul Rubin ♦♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 07 May '15, 06:51

Seen: 741 times

Last updated: 07 May '15, 18:05

OR-Exchange! Your site for questions, answers, and announcements about operations research.