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.
79
questions
2
votes
1
answer
31
views
How to deal with performance bottlenecks in Stochastic Vehicle Routing Problem with Benders' decomposition?
I've been working on solving a stochastic vehicle routing problem using Benders' decomposition with CPLEX in C++. Initially, my implementation struggled with larger instances, but I've made ...
1
vote
1
answer
44
views
Cplex no solution but no conflict
I am solving a problem using benders decomposition. The master problem is solved by cplex.The subproblems are logic and can be solved without using cplex solver. The scale for subproblem is large. ...
1
vote
1
answer
50
views
Fast Algorithms for Min-cost Multicommodity Flow Problem with Most Arcs Having 0 cost
I have a min-cost multicommodity flow problem with the following characteristics:
Flows can be fractional (integer flows not required)
Set of commodity types is $K$, set of demand nodes is $\\{ d_k : ...
2
votes
2
answers
97
views
benders decomposition master problem scale large
I am dealing with a benders decomposition problem, in which there are 100 sub-problems that need to be solved. During each iteration, 100 new optimal cuts will be added to the master problem. I would ...
2
votes
1
answer
151
views
Implementing Logic-based Benders decomposition on a single search tree
Currently, I am working on a scheduling problem and trying to approach it by the logic-based Benders decomposition method. Theoretically, I have everything, i.e., the master and sub problem(s), the ...
3
votes
1
answer
93
views
How to modify Benders decomposition to handle overlapping or shared variables among the subproblems
I have a problem that can be separated into a master problem and two subproblems, SP-A and SP-B. SP-B share some variables with SP-A, and the shared/overlapping variables from SP-A cannot be fixed for ...
2
votes
1
answer
52
views
Is there a way to find out which original constraints are violated when a feasibility cut is generated in benders?
I've been dealing with Benders Decomposition and I've been wondering, if I have an unbounded solution of the dual subproblem, is it possible to find out which constraint from the original problem is ...
1
vote
1
answer
76
views
Benders Decomposition using Cplex
I wanted to know whether the Automatic Benders Decomposition from C-plex allows us to solve the sub-problems in parallel over multiple cores. From what I know, one can set the number of threads in ...
4
votes
1
answer
151
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 ...
1
vote
1
answer
112
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 ...
1
vote
0
answers
41
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 ...
1
vote
0
answers
81
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 ...
1
vote
2
answers
259
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 ...
1
vote
1
answer
91
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 ...
1
vote
1
answer
82
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 ...
0
votes
2
answers
234
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
96
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 ...
0
votes
2
answers
128
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 ...
2
votes
2
answers
78
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 ...
1
vote
2
answers
116
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 ...
2
votes
1
answer
74
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 ...
4
votes
1
answer
375
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
0
answers
44
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
157
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 ...
2
votes
1
answer
182
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 - ...
2
votes
0
answers
66
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) ...
2
votes
1
answer
124
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,...
2
votes
0
answers
75
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 ...
2
votes
1
answer
188
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=\...
1
vote
1
answer
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....
5
votes
1
answer
349
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 ...
3
votes
1
answer
146
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 ...
1
vote
2
answers
305
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
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 ...
6
votes
0
answers
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) ...
2
votes
1
answer
122
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 ...
1
vote
2
answers
218
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 ...
3
votes
3
answers
763
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?
7
votes
2
answers
881
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 ...
4
votes
2
answers
176
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-...
1
vote
0
answers
678
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 ...
3
votes
1
answer
519
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 ...
3
votes
1
answer
126
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 ...
5
votes
1
answer
404
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 ...
5
votes
3
answers
405
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 ...
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 ...
2
votes
0
answers
95
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 ...
2
votes
0
answers
263
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 ...
3
votes
1
answer
311
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 ...
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 ...