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.
71
questions
4
votes
1
answer
117
views
What's the best way to speed up Benders Decomposition for a stochastic vehicle routing problem?
Currently I am working on an implementation of Benders Decomposition that solves a stochastic vehicle routing problem with synchronisation constraints.
Sadly, at the moment it is not performing fast ...
- 139
1
vote
1
answer
89
views
Benchmark problems for Benders Decomposition
we are implementing a scheduling model using Benders Decomposition. Does someone know of any existing implementation of Benders or any repositories that contain continuous or integer problems solved ...
- 11
1
vote
0
answers
34
views
Is there a way to calcuate the maximum number of cuts in a Benders decomposition?
Since the benders algorithm is finite, there a maximum number of cuts that could theoretically be added. The worst case is that I add cuts for all extreme points and all extreme rays that are part of ...
- 139
1
vote
0
answers
80
views
Weird behavior when using Automatic Benders Decomposition in CPLEX
I've encountered some weird behavior when using the Automatic Benders Decomposition in CPLEX.
I initially solved the MIP without BD and then I compared the results against the Full, Workers and User ...
- 111
1
vote
2
answers
113
views
Understanding the L-shaped-method and the different variants of it
I am currently trying to understand the integer L-shaped-method/stochastic version of Benders Decomposition because I have practical problem MIP that is stochastic and thus has very good decomposition ...
- 139
1
vote
1
answer
68
views
How do I check convergence in stochastic Benders?
So in the deterministic version of Benders, the main process works like this:
I initialize my x-vector (Integer variables from the master problem) and solve the dual subproblem (SP).
I add an ...
- 139
1
vote
1
answer
79
views
Recommendations to understand stochastic version of Benders?
I successfully understood and implemented a Benders algorithm for the deterministic version of the problem I am studying.
However, I have some issues now diving into the stochastic model. I have the ...
- 139
0
votes
2
answers
215
views
How to identify constraints that make problem not solvable in polynomial time?
I am reading this paper, available for free viewing, which contains an example of job shop scheduling, shown below.
The details of the variable definitions, etc., can be found in the paper, but it's ...
0
votes
1
answer
75
views
Is an insanely high number of feasibility cuts normal while solving a VRP with Benders?
I am in the process of trying to solve a VRP with synchronization constraints with Benders Decomposition. I am programming in C++ and my approach seems to be really slow for the following reason:
My ...
- 139
0
votes
2
answers
95
views
Tips for implementing Benders Decomposition in C++?
currently I am working on implementing Benders Decomposition for a large-scale stochastic MIP in C++ using the CPLEX Solver. I've been spending the last couple of months learning the programming ...
- 139
2
votes
2
answers
76
views
In Benders Decomposition, do you add an optimality cut together with a feasibility cut?
in the process of implementing my first BD algorithm, I am unsure how to proceed in the case that the subproblem is unbounded.
Obviously, it means you get an extreme ray that you can add to the RMP as ...
- 139
1
vote
2
answers
111
views
Persisting Subproblem Infeasibility Benders Decomposition
I'm currently working on an optimization problem where I'm using Benders decomposition to solve a complex problem involving the installation of charging stations. The master problem determines the ...
- 21
2
votes
1
answer
59
views
How do you derive the Benders feasibility cuts?
starting off with a MIP that I want to solve using Benders.
so in Benders Decomposition, you add feasibility cuts in the following form:
$v^j (b - Ax) \geq 0$
with $j \in J$ being the set of extreme ...
- 139
4
votes
1
answer
307
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 ...
- 139
1
vote
0
answers
41
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 ...
3
votes
1
answer
153
views
About Mathematical Programs
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 ...
user5245
2
votes
1
answer
146
views
Obtaining the dual ray of an infeasible lp to generate a benders feasibility cut
I am struggling to correctly interpret the meaning of a dual ray for an infeasible primal lp.
Consider the following example.
$$
\min z = y_1 + y_2 -2y_3
$$
s.t
$$y_1 -2y_1 -y_3 \ge 3 $$
$$-2y_1 - ...
- 21
2
votes
0
answers
59
views
Automated Benders Using Annotations
I'm trying to solve an optimization model using Automated Benders with annotations using CPLEX library in C++. I've defined a master problem and N (number of supply nodes in my model's network) ...
- 61
2
votes
1
answer
115
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,...
- 61
2
votes
0
answers
73
views
Benders with MINLP subproblem as the pricing problem of Dantzig Wolfe
I have a convex MINLP that after a Dantzig-Wolfe reformulation, passes most of the difficulty onto the pricing problem, which becomes a convex MINLP itself.
The pricing problem should be solvable with ...
- 534
2
votes
1
answer
167
views
Difference between Optimality cuts and Feasibility cuts for L shaped method in stochastic programming?
What is the difference between Optimality cuts and Feasibility cuts for L shaped method in stochastic programming? Like for the following problem they used Optimality cuts,
$$
\begin{aligned}
& z=\...
- 157
1
vote
1
answer
127
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....
user5245
5
votes
1
answer
289
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 ...
- 534
3
votes
1
answer
141
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 ...
- 31
1
vote
1
answer
254
views
Apply Benders decomposition approach in CPLEX with python while using docplex class
I am new to cplex with python. I want to solve a problem using the Benders decomposition approach. Where I want to use UserCutCallback and LazyConstraintCallback. I am writing code in script format (...
9
votes
3
answers
981
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
6
votes
0
answers
208
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) ...
- 109
2
votes
1
answer
112
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
1
vote
2
answers
181
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 ...
- 81
3
votes
3
answers
734
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?
- 81
7
votes
2
answers
797
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 ...
- 81
4
votes
2
answers
173
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-...
- 109
1
vote
0
answers
599
views
How to eliminate large matrix coefficients and large RHS warning in Gurobi
I'm solving a large network flow problem using Gurobi to do Benders decomposition in Python. The imported .csvs contain values that typically fall in either zero, the range of [20,200], or with a ...
- 109
3
votes
1
answer
484
views
Benders decomposition feasibility/ optimality cuts
I am trying to understand Benders Decomposition method. I am reading this book Decomposition techniques in mathematical programming by A Conejo, E Castillo, R Minguez. The book provides an example of ...
- 333
3
votes
1
answer
111
views
Master Problem Infeasible after Iterations of Unbounded Sub Problem (Generic Benders Decomposition in non Stochastic MILP)
I am dealing with a large problem of MILP problem and interested to apply Benders Decomposition. I have already check the original problem and it was feasible to run in large number of computation ...
- 33
5
votes
1
answer
386
views
Optimality in L Shaped or Bender Decomposition
I was working on solving a two-stage stochastic problem using L Shaped method (Benders Decomposition). I have discussed the model here: Stochastic Facility Location Model.
Do the single-cut/ multi-cut ...
- 619
5
votes
3
answers
397
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 ...
- 331
3
votes
1
answer
1k
views
How to compare the optimality gaps between a commercial solver and Benders
Suppose I have a mixed-integer-linear programming model where the objective is maximization. I solve my model in two different ways. First, I call CPLEX (a commercial solver), and then implement ...
- 314
2
votes
0
answers
87
views
Two-stage stochastic with non-linear recourse
I am working on a two-stage facility location problem as I described in this question.
I am solving it with the L-shaped method (Benders decomposition). The cost value between each $(i,j)$ is a ...
- 619
2
votes
0
answers
254
views
About combinatorial Benders Cuts
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 ...
- 331
3
votes
1
answer
288
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 ...
- 619
15
votes
2
answers
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 ...
- 507
2
votes
1
answer
276
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 ...
- 331
2
votes
1
answer
234
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 ...
- 61
3
votes
1
answer
404
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 ...
- 33
7
votes
2
answers
342
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
2
votes
1
answer
157
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 ...
- 55
3
votes
1
answer
839
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 ...
- 67
7
votes
3
answers
989
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
7
votes
1
answer
697
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,396