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

81 questions
Filter by
Sorted by
Tagged with
1k 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 ...
• 1,859
731 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 ...
• 2,418
2k 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 ...
• 2,077
659 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, ...
• 2,917
4k 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 ...
• 517
1k 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) ...
• 314
144 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)$ ...
• 1,859
175 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 ...
• 221
626 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 ...
• 1,661
1k views

### Is Dantzig-Wolfe and Benders' Decomposition still applied in Operations Research?

A year ago, I had taken my master's degree class Optimisation Theory, and we were learning Dantzig-Wolfe Decomposition and Benders' Decomposition. I found it very challenging to use these algorithms ...
• 139
200 views

### Ill-conditioned LP in Benders decomposition

I have implemented a Benders decomposition for a constrained network flow but the LP solver (Gurobi) warns me of the ill-conditioning of the subproblem dual LP. As you can see below, the coefficients ...
1k 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.
• 409
346 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 ...
• 2,150
906 views

### How to find extreme rays

I am applying Benders decomposition and the dual is unbounded. I need to find the extreme rays to proceed, but I am not sure how to do that. Following is an example problem, can someone explain how ...
740 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,451
361 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 ...
• 314
365 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 \\&\...
• 2,150
427 views

• 157
131 views

### multi stage stochastic programming algorithm

I have a multi-stage stochastic programming model. I have 3 groups of variables: the first group takes values at the beginning of the planning horizon before the first realization and does not change ...
• 21
283 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 ...