We changed our privacy policy. Read more.

# 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.

31 questions
Filter by
Sorted by
Tagged with
4answers
727 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 ...
4answers
446 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 ...
4answers
635 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 ...
2answers
416 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, ...
2answers
530 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) ...
1answer
101 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)$ ...
1answer
116 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 ...
2answers
429 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 ...
1answer
1k views

### Is Apple's M1 suitable for Operations Research?

I am curious about the performance of Apple's M1 chip solving optimizations models, MIP, LP, and in solutions approach as benders or columns generations. I read that is a spectacular cpu to perform ...
0answers
142 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 ...
2answers
267 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 ...
1answer
304 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: \...
2answers
187 views

1answer
74 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 ...
1answer
111 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 ...
2answers
242 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\\ &...
1answer
156 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, ...
1answer
161 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 ...
1answer
91 views

### Stochastic Facility Location Model

I am solving a stochastic facility location model using Benders decomposition (L-shaped algorithm). In each scenario, I want to allocate demands from origin to a fixed number of closest open ...
1answer
264 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 ...
1answer
119 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 ...
2answers
147 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-...
1answer
122 views

### Benders Decomposition cuts for MILP problem with further separable subproblems

I am solving an OR scheduling problem where I assign the patient to (day,OR) tuple in Master Problem. Once the assignment is made, a subproblem can be solved for each (day,OR) tuple independently ...
1answer
112 views

### Benders decompositions: Number of iterations does not remain the 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 ...
1answer
85 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 ...
1answer
264 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. ...
0answers
78 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 ...