18 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 ...
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 ...
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 ...
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 ...
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 ...
user avatar
  • 2,410
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 ...
user avatar
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 ...
user avatar
  • 1,045
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 ...
user avatar
10 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 ...
user avatar
  • 938
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 ...
user avatar
  • 2,403
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 ...
user avatar
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 ...
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 (...
user avatar
  • 2,110
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 ...
user avatar
  • 2,665
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)...
user avatar
  • 331
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 ...
user avatar
6 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 ...
user avatar
6 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 ...
user avatar
  • 21.7k
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 ...
user avatar
  • 28.7k
6 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 ...
user avatar
  • 2,110
6 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 ...
user avatar
  • 28.7k
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 ...
user avatar
  • 1,428
6 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 ...
user avatar
  • 28.7k
5 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 ...
user avatar
  • 461
5 votes
Accepted

Can I apply decomposition methods for this scheduling problem

Thank you for adding the formulation. Assuming $\Delta t$ is a nonnegative coefficient, you can simplify the formulation by omitting $h_t^\text{positive}$, $P_t^{\text{Surplus}^-}$, and the ...
user avatar
  • 21.7k
5 votes

Improving cuts from sub-problem with problem-specific hierarchical information

The implied cuts may not be worth adding. Depending on how the solution process goes (solving the master to "optimality" each time before solving the subproblem, versus a "one tree" approach), it ...
user avatar
  • 28.7k
5 votes

Two Genetic Algorithms to solve two subproblems is a bad decision or I'm doing something wrong?

There is a type of GA called a "random key" GA [1] that was originally designed for scheduling problems, with an eye toward dealing with constraints inherent in those problems. I've had some ...
user avatar
  • 28.7k
5 votes

Combinatorial Feasibility Cuts for Benders Decomposition

I'm not aware that either approach is automatically better than the other. Once consideration regarding putting feasibility constraints in the master problem is whether they would likely be violated ...
user avatar
  • 28.7k
4 votes

What are the modern optimization methods for large systems?

It is also my impression that decomposition methods are not widely used in a commercial context. In the industry, you often make an "effort vs. value" estimation to decide what methods to use. This ...
user avatar
4 votes

Decomposition methods for two-stage stochastic program with integer variables

To solve stochastic programming models with integer recourse, there are some methods. Most stochastic programming textbooks cover these methods. For example, chapter 7 of Introduction to Stochastic ...
user avatar
  • 2,410

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