# Tag Info

19

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 generalization of both stochastic and minimax problems), and impose risk constraints (which can serve as convex approximations of probabilistic constraints). As Larry commented above, PYOMO is ...

15

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 that force them to take on better values. In the case where there are no costs in the subproblem, the only issue is feasibility of the $y$ variables. In the ...

14

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 software. So, the following is my own two cents. Dealing with stochastic programming models, usually, you reformulate the problem as a deterministic equivalent ...

14

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 master relaxation involving only a subset of the variables, and (2) a machinery (the Benders cut) based on LP duality to take the remaning variables into account. ...

11

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 the dual"), such methods may significantly differ when looking at the computational side. DW and Lagrangian relaxation also give the same dual bound, and (dual) ...

11

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 increasing number of inequalities, derived from some "dual" information of the other subproblem; while the second problem usually is solved for some variable values ...

10

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 off-the-shelf solvers, so it requires quite some coding to make this work (fast). A recent example of a paper using this method is Zeighami and Soumis (2019), ...

9

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 more oriented towards control problems) StochasticPrograms.jl, rather complete modelling environment SDDP.jl, an implementation of SDDP and a modelling layer ...

9

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 that can be written as LP without relaxing original constraints on integrality of variables. It is even better if that subproblem (or its dual, which is more ...

8

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 f, G(x)y\leq g, x \in \mathbb{Z}^n, y \in \mathbb{R}^+\}$$ as $$\min_{x,y} \{c'x + \Phi(x) \mid Ax \leq b, x \in \mathbb{Z}^n\}$$ with $$\Phi(x) = \min_{y} \... 7 "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 proceeds to give a precise statement of this correspondence. 7 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 (during my Bachelor studies), and I really enjoyed it. Chapter 7 of the book titled THE DECOMPOSITION PRINCIPLE introduces Dantzig-Wolfe decomposition and its ... 6 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 getNcuts() (the issue is there with all CPLEX APIs). The Benders algorithm implemented in CPLEX consists of two main phases. In the first phase, we solve the continuous relaxation of the (... 6 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 practice is that it's impossible to gauge how useful an algorithm/method is without trying it out first, so the most important skill is the skill to do try ... 6 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 decomposition algorithm would terminate because the solution is optimal to the original problem. 6 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 algorithms that relied exclusively on adding cuts to the LP relaxation (no branching). I would consider branch and cut different from logical or combinatorial Benders ... 6 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), following materials are recommended: [carøe1998l], chapter 5.1 in [birge2011introduction] for L-shaped Benders Decomposition, in terms of two-stage (... 6 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 having a single subproblem limit the effectiveness and number of cuts? I don't think so. Is there a benefit to doing it? I think the answer is generally no, with ... 5 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 associated constraints. Instead, you need only impose$$P_t^{\text{Surplus}^+} \ge P_t^\text{PVtotal} - P_t^\text{total} \quad \text{for all $t$} \tag 1 to get the ...

5

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 recently, maybe you can apply some of the findings to your problem. Four promising recent studies and some additional pointers: Rahmaniani, R., Ahmed, S., ...

5

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 might be better to just let the master problem identify the relevant cuts (by generating solutions that violate them). That said, if you are using a solver, it may ...

5

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 luck using it on other types of problems. The gist of the approach is that you establish a chromosome (in your case, a vector with some positions designated ...

5

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 suitable algorithm (primal simplex, dual simplex, etc, whichever is faster for your problem) and then get the dual values (using getDual or getDuals), or you can ...

4

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 will often not favor decomposition algorithms due to a relatively high effort and the risk of it not providing better results. I would make the following ...

4

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 Programming by Birge and Louveux covers these techniques. In particular, I suggest either using the integer L-shaped method or the progressive hedging algorithm (...

4

If I understand the question correctly, it is not possible to have the same optimality cut generated twice because (a) cuts are cumulative and (b) an optimality cut is only generated when an allegedly integer-feasible solution would violate the generated cut. So if you get solution 1, use it to generate cut 1 (which is added to the master), then get solution ...

4

I'll comment on the Lagrangian relaxation question and leave the Benders question for someone else to comment on. (You might want to consider splitting your question into two, one for LR and one for BD.) In my experience, this sort of gap is common. (And frustrating.) There are a few avenues you could go down in order to try to diagnose and maybe fix the ...

4

You need to use a callback, and CPLEX introduced a new callback system ("generic callbacks") in version 12.8 (I think) while maintaining support, at least for now, for the original callback system ("legacy callbacks"). The details of doing the branching depend in part on which system you use. With legacy callbacks, you create a class that ...

4

It would be better to use big-M values that depend on $f$, $a$, and $i$, like $\bar{W}_{f,a,i}$, instead of just on $i$ only. Also, how are you computing big-M? For fixed $x$ and $y$ that satisfy the first two constraints, your original problem is linear and feasible. An alternative approach to linearization is to use combinatorial Benders decomposition, ...

4

If I'm correct in my understanding of the decomposition, the master problem contains the binary variables (and a surrogate variable for the subproblem objective value) and the subproblem contains all the other variables and all the terms of the original objective function. That being the case, you might look at a paper by Codato and Fischetti [1], ...

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