Implicitely fixed (primal) variables in subproblems of Benders Decomposition

 3 3 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 366●2●10 accept rate: 21% 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

 1 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 Rubin ♦♦ 14.6k●5●13 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 1 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 ♦♦
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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

Tags:

×35
×12
×7
×6
×1