5
1

I'm wondering what software implements specialized methods for stochastic integer programs. I've found SPL-IOR implements methods for simple integer recourse, and PySP includes progressive hedging algorithms. I know there are others that write the deterministic equivalent and allow you to give the DE to an existing IP solver. Is there anything else?

I'm working on implementing the D^2 and D^2-BAC algorithms, first described in "The C3 Theorem and a D2 Algorithm for Large Scale Stochastic Integer Programming: Set Convexification" (Sen and Higle, Math Programming, 2005). I'd especially be interested in an existing implementation of these algorithms. Lewis Ntaimo's dissertation does an excellent job of describing them in detail (including pseudocode!), but the implementation is not so trivial.

Thanks!

asked 01 Nov '11, 23:01

Luis%20de%20la%20Torre's gravatar image

Luis de la T...
4231612
accept rate: 11%

edited 01 Nov '11, 23:03

Thanks for the help. There isn't really a clear answer to mark as the 'correct' one but both of these help.

(03 Nov '11, 11:11) Luis de la T...

LINGO 13 can solve stochastic integer programs using DEP (with Monte Carlo sampling). It also offers nested Benders' decomposition for solving stochastic linear programs. The negative point is that it's not free.

DECIS available through GAMS can solve stochastic (non)linear programs through various techniques using other solvers such as CPLEX. However, as far as I know, it cannot solve integer programs as you cannot define stage variables to be discrete. However, looking at its user guide, which describes its solution strategies, might give you some ideas.

Finally, it seems that Solver Foundation has some stochastic programming features, however the MSDN is not very well documented about this and I couldn't find any details about types of problems it can solves or types of algorithms it uses.

Update: As of March 2012, GAMS is offering solution of stochastic programs based on specialized model implementation (EMP reformualtion framework) using different solvers such as DE, DECIS, and LINDO.

link

answered 02 Nov '11, 15:31

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

edited 25 Mar '12, 04:06

I think I read somewhere that Solver Foundation can solve 2-stage recourse problems, but I might be wrong.

(12 Jan '12, 11:29) Samik R.
1

Lingo 12.0 with nested Benders is for the continuous case only.

(24 Mar '12, 13:03) anahita

@anahita: Thanks for correcting the mistake.

(25 Mar '12, 04:12) Ehsan ♦

See ddsip http://www.neos-server.org/neos/solvers/slp:ddsip/LP.html which uses dual decomposition.

link

answered 02 Nov '11, 21:24

Shabbir%20Ahmed's gravatar image

Shabbir Ahmed
1062
accept rate: 33%

edited 02 Nov '11, 21:24

There is an implementation with me which has been reported in Yuan and Sen's Enhanced D^2-BAC paper. We will soon have an general integer version also. For sampling, you may take a look at the SD Project (for continuous SP) https://sites.google.com/a/datadrivendecisions.org/www/

link

answered 12 Jan '12, 01:18

Yunwei's gravatar image

Yunwei
311
accept rate: 0%

Fantastic! Is there a mailing list I can get on for release announcements of your code, or can you post on OR-Exchange when the general integer version is released?

(12 Jan '12, 12:15) Luis de la T...

AIMMS, which comes with free academic license, provide some methods for solving stochastic programming problem (I'm sorry I do not know much in this field)

http://www.aimms.com/operations-research/mathematical-programming/stochastic-programming

link

answered 04 Nov '11, 01:05

NVA's gravatar image

NVA
1015
accept rate: 0%

OptQuest uses tabu search (a meta-heuristic) and can solve stochastic MINLP's. It is a commercial package, available directly from Opttek, or with a few other Monte Carlo simulation packages. For example, Oracle Crystal Ball can perform simulation and stochastic optimization within Excel and has a friendly GUI.

Disclaimer: I work for Oracle Crystal Ball.

link

answered 12 Jan '12, 11:25

Samik%20R.'s gravatar image

Samik R.
1.2k1920
accept rate: 2%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×101
×58
×28

Asked: 01 Nov '11, 23:01

Seen: 3,433 times

Last updated: 16 Jan '14, 07:21

OR-Exchange! Your site for questions, answers, and announcements about operations research.