1
1

Dear All,

I am new to the field of stochastic programming. I am going to formulate and solve a multi-stage stochastic problem by using recourse method.

I wondering if I formulate and solve the deterministic equivalent of the problem, will I get the same answer as the stochastic problem?

asked 04 Apr '11, 23:14

Meysam's gravatar image

Meysam
1313
accept rate: 0%


Part of the answer depends on whether you are talking about theory or whether you are looking for computational results.

Theoretically speaking, it's always possible to formulate a deterministic equivalent. The question is whether that can be solved directly or whether you have to solve it through other means such as sampling, decomposition, etc.

Practically speaking, whether you can solve the deterministic equivalent directly depends primarily on the nature of the random variates: is there a relatively small number of (finite) random variates? This is only true if the random variables have a small number of discrete outcomes. If so, then the deterministic equivalent can be solved as a traditional LP or MIP. If not, then you're better off with sampling methods.

link

answered 04 Apr '11, 23:40

Greg%20Glockner's gravatar image

Greg Glockner
43716
accept rate: 20%

Many thanks Greg! Very helpful and clear answer, indeed!

All I wanted to know was, if I can formulate the deterministic equivalent of a stochastic problem and solve it by using LP/NLP/MIP solvers, OR I have to use a stochastic programming solver. According your answer, I believe I can directly solve the deterministic equivalent bevause I roughly have 10 scenarios (after using scenario reduction algorithm).

(06 Apr '11, 08:36) Meysam

I think your question is somehow flawed. For decision making under risk (via stochastic programming) or uncertainty (via robust optimization), you have to construct a deterministic equivalent problem. In other words, you cannot directly solve a decision making problem with risk or uncertain parameters. Therefore, there is no answer to your question. I think a better question would be:

How can I be assured that my solution technique have a certain level of accuracy?

In other words, does my approach consider all possible realizations of stochastic parameters?

If you have discrete scenarios, then you might use conventional deterministic optimization methods or methods commonly used in stochastic programming such as benders decomposition or L-shaped methods. In this case, you can be sure that you are using very accurate methods (i.e. exact) provided you are able to solve the respective master problem and its subproblems optimally and you have enough time.

If your stochastic parameters have continuous distribution functions, you could try using Monte Carlo-based sampling methods such as sample average approximation, which could provide you with a near optimal solution as well as a statistical lower bound. In this case, the accuracy depends on your sampling method and of course, how much time and computational power you have. The more samples with more scenarios in each sample you generate, your accuracy increases. There are results in the literature based on computational experiments guiding you to determine number of samples and respective number of scenarios in each sample.

link

answered 05 Apr '11, 14:32

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

edited 24 Mar '12, 06:51

Many thanks Ehsan jan! Very helpful and clear answer, indeed!

All I wanted to know was, if I can formulate the deterministic equivalent of a stochastic problem and solve it by using a LP/NLP/MIP solver, OR I have to use a stochastic programming solver. According to your answer, I believe I can directly solve the deterministic equivalent because I roughly have 10 scenarios (after using scenario reduction algorithm).

(06 Apr '11, 08:37) Meysam

Your problem is probably solvable via most of optimization software provided its deterministic version is not very complex (e.g. presence of non-convex functions). There are also some SP solvers such as DECIS, SLP-IOR, and MSLiP. Please see below for a list: stoprog.org/index.html?software.html

(06 Apr '11, 11:33) Ehsan ♦

Yes, this should work though it could be hard if there are lots of scenarios and stages.

I have been working on a pretty simple implementation of Bender's Decomposition for Multistage Stochastic Programs that I can send you if the Deterministic Equivalent gets intractable. The code runs in MATLAB but uses the CPLEX API to solve LPs. I've purposely tried to make user-input as simple as possible.

In general, try to stay away from the SP solvers out there, the SMPS file format will drive you nuts. A better option may be to use AIMMS... This has a very nice stochastic programming implementation but can be a little tricky to learn.

Feel free to e-mail/message me in case you need anything!

link

answered 30 Apr '11, 02:35

Berk%20Ustun's gravatar image

Berk Ustun
3071311
accept rate: 0%

Hi Berk, Could you kindly send me the MATLAB code? I am working on a multi stage SP and the scenarios are getting messier and I am finding it hard to implement Benders. Thanks a ton!

(29 Mar '12, 01:30) rahulsharm9
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:

×58

Asked: 04 Apr '11, 23:14

Seen: 3,969 times

Last updated: 29 Mar '12, 12:10

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