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
1answer
84 views

Benders decompositions: Number of iteration does not remain same

I am solving an LP(i.e 118-bus system economic dispatch for 130% loading) using benders decomposition. The problem takes 26 iterations to converge. This means that the process adds 25 cuts to the ...
3
votes
1answer
58 views

Benders Decomposition for deterministic MILP

When I think of Benders Decomposition, I typically think of two-stage stochastic programs. However, I was wondering if there is any application to decomposing a large scale deterministic MILP with ...
5
votes
1answer
86 views

Logic-based Benders decomposition with integer master variables

I am looking for a paper/study in which a Logic-based Benders decomposition (LLBD) framework is used when the master problem is associated with integer variables (not specifically binary). In general ...
2
votes
1answer
78 views

Numerical problem regarding to classical benders cut of large scale problem

I am trying to implement benders decomposition for a simple two stage unit commitment problem. I implemented the classic Benders decomposition to add feasible cut and optimal cut to relax master ...
3
votes
1answer
212 views

Implementing benders decomposition using Lazy and User cuts callback of Cplex

I am trying to implement benders decomposition for a simple fixed charge transportation problem for the purpose of learning. I implemented the classic Benders decomposition successfully by adding ...
5
votes
3answers
560 views

Textbook recommendation for linear programming decomposition fundamentals

I am looking for a textbook on linear programming decomposition fundamentals. The book should be clear and easy-to-follow for self study and should include examples to illustrate the concepts.
6
votes
1answer
277 views

Classical Benders decomposition algorithm implementation details

Given the following problem: \begin{align} P: \min_{x,y}&\quad c^\top x+f^\top y\\ \text{s.t.}&\quad Ax+By=b\\ &\quad y\in Y\\ &\quad x\geq 0 \end{align} Problem $P$ is equivalent to: \...
3
votes
1answer
101 views

Logical / combinatorial Benders Decomposition vs Cutting plane method

Is there a difference between logical and combinatorial Benders Decomposition and the cutting plane method? My understanding is that for all of these techniques, there is a MIP and based on solutions ...
2
votes
2answers
142 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
125 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
155 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
220 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\\ &...
1
vote
0answers
75 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
508 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
109 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
150 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
257 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
151 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
176 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
262 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
99 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
112 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
423 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
400 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
137 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
603 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
435 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
705 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 ...