19 votes

Stochastic programming MIP solvers

If you have access to MATLAB, I can recommend Marietta (I am a developer of this toolbox), with which you can solve general risk-averse optimal control problems (a ...
Pantelis Sopasakis's user avatar
15 votes
Accepted

How to determine if a given problem seems to be a good fit to be solved using combinatorial Benders decomposition

In combinatorial Benders, where $x$ are the variables in the master problem and $y$ the variables in the subproblem, the purpose of the subproblem is to come up with constraints on the $x$ variables ...
Michael Trick's user avatar
15 votes
Accepted

Is Apple's M1 suitable for Operations Research?

One problem you might encounter is that the many solvers are either not available for M1 like CPLEX[1]. M1 support for Gurobi might be mixed in general due to issue like "Only use single-threaded ...
worldsmithhelper's user avatar
15 votes

Is Dantzig-Wolfe and Benders' Decomposition still applied in Operations Research?

I don't know about "commonly" used, but Benders is still definitely in use, and I'm pretty sure D-W also is. Benders in particular has evolved beyond the original version created by Jack ...
prubin's user avatar
  • 38.8k
14 votes

What are the modern optimization methods for large systems?

The gap between industry and academia is huge. My suggestion for a future professional would be to learn very good coding because without that skill people are very limited. What I have seen in ...
Nikos Kazazakis's user avatar
14 votes

How to determine if a given problem seems to be a good fit to be solved using combinatorial Benders decomposition

Talking about general Benders (and Geoffrion for general convex), my student @Fischenders suggested the following slides An important remark is that Benders introduced TWO ideas: (1) working on a ...
Matteo Fischetti's user avatar
13 votes

Stochastic programming MIP solvers

Disclaimer: I'm not a researcher in the area of stochastic programming software. But as a researcher in the area of stochastic programming, I've put some time into looking for stochastic programming ...
Ehsan's user avatar
  • 2,448
11 votes

Relationship between Benders decomposition and Dantzig-Wolfe decomposition

My experience is that even when two methods "are equivalent" (eg in the sense that they give the same dual bound), and even though they may be technically "the same" (like "Benders is DW applied to ...
Marco Lübbecke's user avatar
11 votes

Stochastic programming MIP solvers

I don't know if it's really what you are asking for, but Julia has a few packages that implement algorithms for stochastic programming (on top of other LP solvers): StochDynamicProgramming.jl (seems ...
dourouc05's user avatar
  • 998
11 votes

How to determine if a given problem seems to be a good fit to be solved using combinatorial Benders decomposition

My way of understanding (Benders) decomposition is that you rather solve (two) separate problems repeatedly than your original problem once. One of the two subproblems has to be resolved with an ...
David Bernal's user avatar
  • 1,075
10 votes

How to handle an IP sub-problem with an objective function in Benders Decomposition

It is possible to have an integer subproblem with an objective, but to solve such a problem you need to branch on variables both in the master problem and in the sub-problem. This is not supported by ...
Rolf van Lieshout's user avatar
10 votes

Is Apple's M1 suitable for Operations Research?

We at Mosek has started porting Mosek to the Apple M1 CPU so the upcoming version 10 will support it. Here is an initial thought. Normally optimization software links to a BLAS/LAPACK library such as ...
ErlingMOSEK's user avatar
  • 3,101
10 votes

Is Dantzig-Wolfe and Benders' Decomposition still applied in Operations Research?

If you search for "Dantzig Wolfe" on Google Scholar, and remove all articles before 2022, you still have 427 papers that come out. So I think it is safe to say that DW is still popular and ...
Kuifje's user avatar
  • 13.2k
9 votes

How to determine if a given problem seems to be a good fit to be solved using combinatorial Benders decomposition

Most importantly, you need to define a subproblem that you can solve as LP without violating integrality constraints. In many mixed integer programs, it is not possible/sensible to find a subproblem ...
J Fabian Meier's user avatar
8 votes

Do Benders cuts exclude current solutions?

It depends on whether you consider the master variable $\eta$ to be part of the solution. You can get the same master $x$ with a different $\eta$ after adding an optimality cut, but then the Benders ...
RobPratt's user avatar
  • 31.5k
8 votes
Accepted

Benders subproblem feasible region dependent upon solution master problem

I always find it helpful to look at Benders decomposition from a primal view, as detailed in this presentation by Matteo Fischetti. You can write $$ \min_{x,y} \{c'x + y \mid Ax \leq b, Dx + Ey \leq ...
Kevin Dalmeijer's user avatar
8 votes

Textbook recommendation for linear programming decomposition fundamentals

I propose reading the following textbook: Linear Programming and Network Flows by by Hanif D. Sherali, John J. Jarvis, and M. S. Bazaraa I read the first 7 chapters of the book a long time ago (...
rasul's user avatar
  • 2,140
7 votes

Relationship between Benders decomposition and Dantzig-Wolfe decomposition

"Benders’ decomposition is Dantzig-Wolfe decomposition applied to the dual" is the first sentence of Section 10.3 in Dantzig & Thapa's Linear programming 2: theory and extensions, which then ...
Marcus Ritt's user avatar
  • 2,715
7 votes
Accepted

Classical Benders decomposition algorithm implementation details

Yes, there is no need to solve π‘Ÿπ‘Žπ‘¦(𝑦) to obtain an extreme ray as you mentioned. In CPLEX, for example, you can use a method called getRay (see here). You can solve the primal problem using a ...
rasul's user avatar
  • 2,140
7 votes

Textbook recommendation for linear programming decomposition fundamentals

I took the course 42136 for Benders decomposition and Dantzig-Wolfe (DW) decomposition at Technical University of Denmark. Besides the textbook [conejo2006decomposition] (mentioned by @A.Omidi as well)...
Edward's user avatar
  • 391
7 votes
Accepted

Benders Decomposition for deterministic MILP

Is there a name for this? Yes: Benders decomposition. I'm pretty sure the seminal work by Jack Benders (1962) had only a single LP subproblem (and was most definitely deterministic in nature). Does ...
prubin's user avatar
  • 38.8k
7 votes
Accepted

Benders decomposition feasibility/ optimality cuts

$\alpha$ is a surrogate for $-y$, so the negative of any valid upper bound on $y$ is a valid lower bound on $\alpha$. You need such a bound since otherwise the master problem would be unbounded (pick ...
prubin's user avatar
  • 38.8k
7 votes
Accepted

Unbounded master problem in Benders decomposition

Assuming your master problem is to minimize $\eta$, a simple way to avoid unboundedness, even before adding any cuts, is to impose a redundant lower bound $\eta \ge L$ for some constant $L$. Often, ...
RobPratt's user avatar
  • 31.5k
7 votes

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

In the paper that proposed L-shaped method, you can find In section 2, an algorithm which is essentially the same as the algorithm developed by Benders[3] is described and a geometric interpretation ...
Penghui Guo's user avatar
6 votes

CPLEX Auto-Benders: How do I get the number of optimality and feasibility cuts?

About the issue you reported on the function getNcuts(), we looked at it and I can confirm that we have a bug in the number of Benders cuts reported by the function ...
Andrea Tramontani's user avatar
6 votes
Accepted

How to handle an IP sub-problem with an objective function in Benders Decomposition

I was researching the topic with mixed-integer subproblems in the context of two-stage stochastic programs, but got stuck and haven't revisited. In the mixed-integer case, there has been some progress ...
ktnr's user avatar
  • 491
6 votes
Accepted

Logical / combinatorial Benders Decomposition vs Cutting plane method

I'm going to assume that "the cutting plane method" refers to branch and cut (branch and bound with cuts added at the root and possibly other nodes), as opposed to older cutting plane ...
prubin's user avatar
  • 38.8k
6 votes
Accepted

Optimality in L Shaped or Bender Decomposition

As far as I can see you have binary variables in the first stage and general integer variables in the second stage. This means that classical Benders cuts (based on duality of the subproblems) do not ...
k88074's user avatar
  • 1,661
6 votes
Accepted

How to find extreme rays

Plot the region in two dimensions, as shown here, where $(x,y)$ corresponds to $(u_1,u_2)$. The second and third constraints have boundary lines with slopes $2/3$ and $3/1$, yielding the extreme rays $...
RobPratt's user avatar
  • 31.5k
6 votes

Unbounded master problem in Benders decomposition

Yes, it is possible in theory. An alternative to bounding the objective function is bounding the variables. If this is a "real-world" model (where the variables represent actual decisions), ...
prubin's user avatar
  • 38.8k

Only top scored, non community-wiki answers of a minimum length are eligible