# 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,227
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,321

### 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,606

### 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,410

### 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,779

### 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,045

### 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,244

### 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 ...
• 938

### 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,403

### 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,002
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 ...
• 5,873

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

### 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,665

### 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)...
• 331

### 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 ...

### 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.1k

### 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 ...
• 21.7k
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 ...
• 28.7k
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,110
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 ...
• 28.7k
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,428
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 ...
• 28.7k
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 ...
• 461
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 ...
• 21.7k

### 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 ...
• 28.7k

### 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 ...
• 28.7k

### 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 ...
• 28.7k