Questions tagged [benders-decomposition]

For questions related to Benders decomposition, a type of optimization algorithm in which certain variables are optimized in a "master problem," the values of those variables are fixed, the remaining variables are optimized in a "subproblem," cuts are generated to be added to the master problem, and the method repeats.

Filter by
Sorted by
Tagged with
2
votes
2answers
130 views

Two Genetic Algorithms to solve two subproblems is a bad decision or I'm doing something wrong?

I'm developing a heuristic based on U-NSGA-III and GA for continuous variables with a crossover operator from this article: https://www.researchgate.net/publication/331451524_CAM-...
4
votes
2answers
89 views

Benders subproblem with product of continuous and discrete variables

I am trying to solve the following problem. The decisions in the problem are $x, y, v, $ and $W$, where $x, y$ are binary and $v, W$ are continuous variables. \begin{equation}\label{eq:3} \begin{...
3
votes
1answer
127 views

Implementation of Local Branching

I've been recently reading some papers where the authors use local branching specifically in Benders Decomposition (see for reference). Although I understand up to some extend how the algorithm works, ...
3
votes
2answers
187 views

Decomposition methods for two-stage stochastic program with integer variables

In a stochastic programming problem, I have binary variables in the second stage. As an example, consider that the optimization problem is given by: \begin{align} &\text{minimize} &\gamma\\ &...
0
votes
0answers
59 views

Benders Decomposition Problem

$$r_{m_h,s}(n)=\frac B{m_hb_\ell s}\log_2(1+\gamma_{m_h,s}(n))$$ How to deal with multiple subproblems in Benders decomposition when the original objective function is in product form of an integer ...
12
votes
2answers
442 views

How to handle an IP sub-problem with an objective function in Benders Decomposition

I have a question on Benders Decomposition (BD). Suppose I have an MILP model which can be decomposed into a master problem (MP) including integer and continuous variables and a subproblem (SP) ...
3
votes
1answer
74 views

Benders implementation on Cplex is very slow

I'm working on a location problem and I have an issue with the Benders decomposition. I'm using Cplex with Python. I coded a single cut and a multi-cut to compare. The single-cut implementation takes ...
3
votes
1answer
121 views

Accessible introduction to L-shaped methods/Benders decomposition

I am looking for papers or other resources that provide an accessible introduction to L-shaped methods/Benders decomposition for solving stochastic linear programming-ideally something focused more on ...
1
vote
1answer
240 views

Can I apply decomposition methods for this scheduling problem

I have a centralized optimization problem for a residential area in the context of a smart grid and load flexibility. So let's say I have 10 buildings and each of them has an electric heating device. ...
5
votes
2answers
117 views

Lagrangian Relaxation for Two-Stage Stochastic Program

I have a two-stage stochastic program as follows: \begin{align}\max&\quad f^\top y+\sum_{s}p_sc_s^\top x_s\\\text{s.t.}&\quad Ay=b\\&\quad W_sX_s+Ty \le h_s \quad \forall s \in S \\&\...
6
votes
2answers
111 views

How to handle bigM in sub-problem of benders decomposition?

Suppose you want to solve a MIP with Benders decomposition and the binary variables ($y_i$) are fixed in the master problem but these variables are used in the sub-problem with bigM like $x_{ij} \le M....
7
votes
2answers
237 views

Do Benders cuts exclude current solutions?

I am wondering if optimality cuts in Benders algorithm exclude the possibility to have the same solutions and as a result, have the same optimality cut? I don't know why it is not possible to have the ...
12
votes
1answer
85 views

Benders subproblem feasible region dependent upon solution master problem

Suppose I want to solve a naturally MINLP problem of the following form: $$ \min_{x,y} \{c'x + y \mid Ax \leq b, Dx + Ey \leq f, G(x)y\leq g, x \in \mathbb{Z}, y \in \mathbb{R}^+\} $$ Here $G(x)$ ...
12
votes
1answer
97 views

Improving cuts from sub-problem with problem-specific hierarchical information

I'm solving an assignment-alike problem with a Logic-based Benders decomposition-alike (LBBD) method. The master problem provides an assignment, which is checked in the sub-problem. Define the set of ...
11
votes
2answers
344 views

CPLEX Auto-Benders: How do I get the number of optimality and feasibility cuts?

I am using CPLEX's 12.9 auto-Benders decomposition feature (from the CPLEX Java API). Following the documentation I let CPLEX decide the decomposition strategy as ...
14
votes
2answers
359 views

What are the modern optimization methods for large systems?

I came across the preface of Optimization Theory for Large Systems (you can read it in Amazon). The author claims in the table (page v) that some of the methods such as Dantzig Wolfe decomposition, ...
9
votes
0answers
123 views

Ill-conditioned LP in Bender's decomposition

I have implemented a Bender's decomposition for a constrained network flow but the LP solver (Gurobi) warns me of the ill-conditioning of the slave dual LP. As you can see below, the coefficients seem ...
16
votes
4answers
457 views

Relationship between Benders’ decomposition and Dantzig-Wolfe decomposition

It’s often said that “Benders’ decomposition is Dantzig-Wolfe applied to the dual”. How can this statement be made precise? I know that in Dantzig-Wolfe, cuts are added in one-to-one correspondence ...
23
votes
4answers
387 views

How to determine if a given problem seems to be a good fit to be solved using combinatorial Benders decomposition

Combinatorial Benders decomposition is a mathematical programming technique consisting into dividing a problem into a master problem and a sub problem. The master problem is solved to optimality (or ...
25
votes
4answers
599 views

Stochastic programming MIP solvers

I am aware that Benders Decomposition is readily available in CPLEX and in SCIP; but are there any (free) solvers that provide off the shelf stochastic programming MIP algorithms or a nice to work ...