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 ...
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 ...
- 2,362
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 ...
- 3,965
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 ...
- 37.5k
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 ...
- 1,646
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 ...
- 2,438
13
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 ...
- 11.9k
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 ...
- 5,889
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 ...
- 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 ...
- 1,065
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 ...
- 2,295
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 ...
- 2,946
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 ...
- 12.8k
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 ...
- 1,100
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 ...
- 29.8k
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 ...
- 6,033
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 (...
- 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 ...
- 2,705
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 ...
- 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)...
- 381
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 ...
- 37.5k
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 ...
- 37.5k
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, ...
- 29.8k
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 ...
- 700
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 ...
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 ...
- 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 ...
- 37.5k
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 ...
- 1,621
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 $...
- 29.8k
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), ...
- 37.5k
Only top scored, non community-wiki answers of a minimum length are eligible