I am aware that Benders Decomposition is readily available in CPLEX and in SCIP; but are there any (free) solvers that provide off the shelf stochastic programming MIP algorithms or a nice to work with programming environment ?
$\begingroup$
$\endgroup$
5
asked May 30, 2019 at 22:41
-
1$\begingroup$ Maybe this helps: yalmip.github.io/tutorial/integerprogramming Yalmip is pretty good at reformulating MIP problems, and give to the relevant solver regarding the availability of solvers in your PC $\endgroup$– independentvariableCommented May 30, 2019 at 22:46
-
1$\begingroup$ Pyomo does something similar. But again, this is about the modeling, not the solution algorithm. $\endgroup$– LarrySnyder610Commented May 30, 2019 at 22:48
-
1$\begingroup$ Here is a nice tutorial (with example code) on how to implement Benders decomposition in Julia/JuMP: juliaopt.org/notebooks/… They have solutions for adding the cuts in a loop and as lazy constraints $\endgroup$– NikoCommented May 30, 2019 at 22:50
-
1$\begingroup$ Does anyone know such solver that can be called with C++? $\endgroup$– Michiel uit het BroekCommented May 30, 2019 at 22:52
-
$\begingroup$ AFAIK, GAMS software has a nice facility to handle stochastic programming. Would you see this? $\endgroup$– A.OmidiCommented May 22, 2020 at 13:06
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
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 perhaps the most popular software for stochastic programming.
Other than that, you can also use any solver directly. If you problem is convex, you can use CXV (in MATLAB) or CVXPy (in Python). Both are very mature software, well documented and with a strong community. CVX is not a solver, though - it is a modelling framework that allows one to interface solvers such as Gurobi (you can obtain an academic licence), SCS, SuperSCS (free open source), IPOPT, CPLEX and many other.
Similarly, you can try YALMIP in MATLAB, which, like CVX/CVX is a popular and convenient modelling framework.
answered May 30, 2019 at 23:21
-
$\begingroup$ CVX is not interfaced to IPOPT or CPLEX (but YALMIP is, among many other solvers).. $\endgroup$ Commented Aug 11, 2019 at 16:22
$\begingroup$
$\endgroup$
1
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 problem (DEP). Then, two scenarios might happen. If your original deterministic problem is not too large and/or you don't have to consider too many scenarios, you can solve the DEP directly using a powerful LP or MIP solver. If that is not the case, you go for stochastic programming algorithms (e.g., L-shaped method, PHA, etc.) that make perfect use of special structures of stochastic programs.
Following the above explanation, generic implementations of stochastic programming algorithms can be classified into two classes of DEP_Generator (i.e., only generates the DEP for a stochastic programming model declaration and then pass it to a general solver without using the special structure of stochastic programs) and DEP_Generator+Algorithms (i.e., generates the DEP and then solves it using a specialized algorithm).
AFAIK, these two classes of solvers are usually implemented for stochastic linear programs. The only three solvers for "stochastic integer programs" of which I'm aware are DE and DECIS both available in GAMS and SLP-IOR (I think SLP-IOR just covers models with simple integer recourse). I think the reason that we don't see "many" generic implementations of stochastic integer programming algorithms is that they are harder-to-solve problems on which generic algorithms do not necessarily perform well. To make these algorithms work, you usually need some knowledge about the problem structure, which is something problem dependent. In addition, the solution of stochastic integer programs usually requires more complex algorithms (e.g., branch and cut or Lagrangian duals).
In case you are interested in stochastic linear programming solver, you might find SMI as an example of DEP_Generators and FAST and MSLiP as examples of DEP_Generator+Algorithms.
-
3$\begingroup$ To add to this answer: there's a 2012 paper by Zverovich et al (see page 23 of link.springer.com/article/10.1007/s12532-012-0038-z) which shows that for very small SPs solving a deterministic equivalent via simplex is fastest, for small SPs solving a deterministic equivalent via an IPM is fastest, and for larger size problems using the level method is fastest (see link.springer.com/article/10.1007/BF01585555). If you are using say Julia/JuMP then you should be able to implement the level method without too much difficulty. $\endgroup$ Commented Jun 4, 2019 at 2:43
$\begingroup$
$\endgroup$
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
- StructJuMP.jl is a modelling layer for block-structured optimisation programs, that can then be solved with StructDualDynProg.jl (implementing SDDP)
$\begingroup$
$\endgroup$
We recently had a review paper on the software packages for Benders decomposition and dual decomposition. We did some benchmark studies on their performance as well through the stochastic programming library. You can find the paper from the link below: http://www.optimization-online.org/DB_HTML/2019/07/7269.html
