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
3 votes
1 answer
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
1 answer
60 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
0 answers
100 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) ...
1 vote
0 answers
65 views

CPLEX gets stuck in "Performing restart"

During solving my problem using generic lazy cuts (in Benders decomposition fashion), the solver gets stuck logging out "Performing restart 2" for several hours (while the time limit is 30 ...
2 votes
1 answer
58 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
97 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
47 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
2 answers
315 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 (...
2 votes
1 answer
160 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 ...
2 votes
2 answers
98 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 ...
4 votes
1 answer
156 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 ...
3 votes
1 answer
96 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 ...
1 vote
1 answer
82 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 ...
2 votes
1 answer
54 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
114 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
2 answers
304 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
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
82 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
1 answer
83 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
238 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
99 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
137 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
83 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
120 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
79 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
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
0 answers
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 ...
7 votes
2 answers
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 ...
18 votes
2 answers
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, ...
18 votes
4 answers
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 ...
5 votes
3 answers
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 ...
9 votes
0 answers
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 ...
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
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,...
2 votes
1 answer
193 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
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
191 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
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 ...
3 votes
1 answer
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 ...
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
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 ...
14 votes
3 answers
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) ...
3 votes
3 answers
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
2 answers
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 ...
7 votes
2 answers
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 ...
4 votes
2 answers
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-...
3 votes
1 answer
531 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 ...
1 vote
0 answers
708 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 ...