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.

Filter by
Sorted by
Tagged with
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 ...
Arctic_Skill's user avatar
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. ...
XXia's user avatar
  • 49
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 : ...
graphtheory123's user avatar
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 ...
XXia's user avatar
  • 49
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 ...
Amir Hosseini's user avatar
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 ...
user4444's user avatar
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 ...
Arctic_Skill's user avatar
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 ...
Vivek's user avatar
  • 21
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 ...
Arctic_Skill's user avatar
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 ...
Vivek's user avatar
  • 21
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 ...
Arctic_Skill's user avatar
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 ...
CHE's user avatar
  • 113
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 ...
Arctic_Skill's user avatar
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 ...
Arctic_Skill's user avatar
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 ...
Arctic_Skill's user avatar
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 ...
somewhere's user avatar
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 ...
Arctic_Skill's user avatar
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 ...
Arctic_Skill's user avatar
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 ...
Arctic_Skill's user avatar
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 ...
bcoulier's user avatar
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 ...
Arctic_Skill's user avatar
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 ...
Arctic_Skill's user avatar
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 ...
Samira Fallah's user avatar
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 ...
user avatar
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 - ...
Kit Searle's user avatar
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) ...
Vala's user avatar
  • 61
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,...
Vala's user avatar
  • 61
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 ...
J. Dionisio's user avatar
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=\...
falamiw's user avatar
  • 157
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....
user avatar
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 ...
J. Dionisio's user avatar
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 ...
BftA's user avatar
  • 31
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 (...
Mohammad Samiullah's user avatar
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 ...
dozgunay's user avatar
  • 139
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) ...
Enthusiast's user avatar
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 ...
mahgol's user avatar
  • 21
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 ...
htam_ujn's user avatar
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?
htam_ujn's user avatar
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 ...
John Bolton's user avatar
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-...
Emma Kuttler's user avatar
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 ...
Emma Kuttler's user avatar
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 ...
Jonn's user avatar
  • 333
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 ...
Lizard White's user avatar
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 ...
mars's user avatar
  • 629
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 ...
Amogh Bhosekar's user avatar
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 ...
whitepanda's user avatar
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 ...
mars's user avatar
  • 629
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 ...
Amogh Bhosekar's user avatar
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 ...
mars's user avatar
  • 629
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 ...
orpanter's user avatar
  • 517