Tag Info

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 ...
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,352
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 ...
• 4,037

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 ...
• 39.6k

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 ...
• 12.2k

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,696

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,463

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,929

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

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,075

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,325

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 ...
• 3,206

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 ...
• 13.5k

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,110

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 ...
• 32.8k
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,212

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,150
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 ...
• 39.6k

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,725
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,150

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)...
• 391
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 ...
• 39.6k
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, ...
• 32.8k
Accepted

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 ...
• 764

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 ...
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
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 ...
• 39.6k
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,691
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 \$...
• 32.8k