# 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
77 views

### Benders Decomposition Implementation - Should I keep the old feasibility cut in master problem?

I am currently working on combinatorial subproblems. First, I need to solve the master problem, find all possible subproblems, solve each combination individually, and ensure all the subproblems are ...
1 vote
60 views

387 views

### Is Benders decomposition and the L-shaped method the same algorithm?

I've been studying the Benders decomposition method to solve stochastic integer problems. I've also stumbled across papers using a so called L-shaped-algorithm which also divides into master problem ...
1 vote
45 views

### Seeking Assistance with Applying Benders Technique for Bilinear Problem Solving

I have two specific types of bilinear terms in the problem. The first type involves the multiplication of an integer variable and a continuous variable, while the second type involves the ...
359 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 ...
658 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, ...
1k 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 ...
409 views

### Combinatorial Feasibility Cuts for Benders Decomposition

Are there any advantages of adding constraints in the Benders master problem that ensure the feasibility of the subproblems? This would not add any feasibility cuts. Or is it beneficial to have a ...
199 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 ...
157 views

I am dealing with the following problem as follows. $$\min \sum_{i,j}( x_{i}+y_{j}+q_{ij}+w_{i})$$ $$\text{s.t.} x_{i}+y_{j}+q_{ij}+w_{i} \geq b_{ij}, \forall i,j$$ Is it possible to handle this ...
129 views

### How should I implement Benders Decomposition with annotations in C++ using CPLEX library

I'm a beginner in C++ and want to implement Benders decomposition in C++ using CPLEX. I'm gonna use it for a special case study, so I need to customize the cuts to minimize the optimality gap. However,...
193 views

1 vote
128 views

### Further decomposing master problem in benders

In the benders decomposition, is it possible to decompose the master problem as follows and let the subproblem become the subproblem of the new subproblem? Let's say that we have the following problem....
365 views

### Dantzig-Wolfe vs Benders Decomposition on the dual problem - Computational differences

My question is a follow-up to this one: Relationship between Benders’ decomposition and Dantzig-Wolfe decomposition. Here what is being discussed is the relationship between the two methods, and it is ...
149 views

### Benders Decomposition for Fixed Charge Transportation Problem

I am trying to write down the steps in Benders decomposition for the Fixed Charge Transportation Problem and was hoping someone could confirm/deny whether my understanding of it is correct. The ...
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 ...
210 views

### Benders decomposition for a dense MILP

I am trying to solve a large MILP, but it seems like dense problems can be very difficult for moderns solvers. I tried to solve the problem described below considering only constraints (1) and (2) ...
129 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 ...
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) ...
770 views

### Unbounded master problem in Benders decomposition

After a few iterations, my master problem with optimality cuts is still unbounded. I wonder if it's possible in theory? If it's possible, how to deal with the unbounded master problem?
1 vote
234 views

### Adding cuts doesn't change the solution of master problem in Benders decomposition

From the problem Unbounded master problem in Benders decomposition, it can happen that after adding cuts the master problem is still unbounded. The answers in the post suggest adding bound for the ...
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 ...
177 views

### How to fix unbalanced multi-commodity network flow with equal supply and demand?

I have a fairly large network with eleven commodities and arc capacities that are commodity-dependent (i.e. an arc may have a higher capacity for one commodity than another). I'm solving a protection-...