12
$\begingroup$

There are many naturally multi-stage (i.e., more than two) stochastic programming problems that are approximated by a two-stage stochastic programming model due to the complete intractability of the 'real' model. For example, consider a 10 period location-transportation problem with some dependencies between the periods so that the solution of one of the periods determines possible recourse actions for the period thereafter. With a two-stage approximation I imply that we consider, in terms of location-transportation, a first-stage decision where we determine the locations to be opened in a first-stage decision. Then, we act as if all information of the 10 periods is presented to the decision-maker, and we make transportation plans for the upcoming 10 periods as a single second-stage decision. The 'real' model here would be a 10-stage stochastic program, but is intractable for many applications (the location-transportation might actually be a problem that is 'relatively' easy, so don't take it to literally)

So, we act as if all uncertainty regarding all future states is revealed after the first stage decision, and this first-stage decision is taken for all future periods directly. Then this approximation can be used in a rolling horizon fashion to guide dynamic decision support. I think (am I correct?) this is a generally accepted method to approach such problems.

Are there any tips and tricks to do so? For example, it feels intuitive to add more weight to nearby decisions than to decisions that are still far away:)

$\endgroup$
6
  • 1
    $\begingroup$ Somehow, I could not add new tags while using the Stack app, and not adding any tags is not possible;) Sorry! $\endgroup$ Commented May 30, 2019 at 22:24
  • 1
    $\begingroup$ I tried adding [stochastic-programming] but it wouldn't allow me to do it without also changing 6 characters in the post itself, which I was reluctant to do. Maybe a mod can? $\endgroup$ Commented May 30, 2019 at 22:43
  • $\begingroup$ Go ahead! I think I lack reputation :( $\endgroup$ Commented May 30, 2019 at 22:44
  • $\begingroup$ Are you discussing an alternative approach to solve multi-stage stochastic programs? I think the nested decomposition is doing what you're describing, but I suspect you have something else in mind. Could you provide a reference for this idea or elaborate more? Thanks. $\endgroup$
    – Ehsan
    Commented May 31, 2019 at 7:32
  • $\begingroup$ I elaborate a bit more on the question. Thanks $\endgroup$ Commented May 31, 2019 at 11:11

1 Answer 1

8
$\begingroup$

Let me first distinguish between two-stage and multi-stage models by emphasizing on two issues, namely the type of uncertainty covered by each model and the sources of stochastic parameters. In two-stage models, you have to assume that stochastic parameters are stationary after being observed. On the other hand, multi-stage models assume a non-stationary behavior. Regarding the sources of stochastic parameters, they usually come from either historical data (usually translated into probability distributions or scenario) or experts’ judgment (directly translated into a small number of scenarios).

Following the case of scenarios created by experts, I believe your only option is two-stage stochastic programming models as it is hard, if not impossible, to create valid scenarios corresponding to a non-stationary behavior. This is usually the case for strategic problems where only a few scenarios are considered in detail. Now if you have enough historical data to fit probability distribution functions or create meaningful scenarios, you have to decide your modeling approach (i.e., choosing between two- stage and multi-stage models).

Now, let’s review the issue of stochastic parameters behavior. A stationary behavior is usually modeled as a two-stage stochastic program. This is in accordance with the way we make a decision. You anticipate some uncertainty and take some precautions. Then you observe a realization of uncertainty and react accordingly and correct your mistakes (i.e., known as the recourse action in SP literature). A non-stationary behavior is better modeled as a multi-stage stochastic program. Here, you’re making some day-to-day decisions, such as financial trading, inventory control, or vehicle routing. Let’s take the example of financial trading. Each day, you invest in some assets, gain/lose some money due to uncertainty realized that day. Then, you keep/change your position in anticipation of what is going to happen tomorrow (which might not be similar to what happened today).

Your location-transportation problem is a good example of two-stage models, where you invest before knowing customers’ demands and then react (i.e., change your transportation plan) in accordance with customers’ actual demands. Here, even if you model the problem as a multi-stage problem, all stages after the first one look the same as they are essentially doing the same thing (i.e., transporting goods from warehouses to customers in the later stages vs. building warehouses in the first stages). The only way you could make this problem a multi-stage one is to assume that you could build new warehouses in every stage.

Based on the above, I don’t think a multi-stage problem could be correctly modeled as a two-stage problem. In addition, I've not seen your described approach formally stated anywhere in the literature before. Although it seems to be a practical heuristic for solving a complex problem. However, following the above discussion, I do not think it is necessarily a very good heuristic for the inherently operational problems. Finally, I think reading section 1.5 of King and Wallace's "Modeling with Stochastic Programming" could shed more light into your question.

PS. As one might confuse the notion of time periods and stages in stochastic programming, I refer them to the following paragraph from King and Wallace's book on page 16.

“We should not confuse information stages with time periods. Stages model the flow of information; time periods represent the ticking of the clock in a model. Stages, on the other hand, are points in time where we make decisions in the model after having learned something new.”

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.