15
$\begingroup$

There are many approaches to deal with the uncertainty such as stochastic programming, robust optimization and fuzzy programming. Finding a suitable approach that is applicable in the real situations can be tricky.

I have two main questions:

1- In general, what are the conditions to use Stochastic Programming in favor of Robust Optimization?

2- When we should model the uncertain parameters with discrete scenarios instead of their probability distributions?

$\endgroup$
8
$\begingroup$

Regarding your first question, I think other answers have summed it up pretty good. Two things I would add are as follows:

  1. Stochastic programming models (besides chance constraint/probabilistic programming ones) allow you to correct your decision using the concept of recourse. In this idea, you have to make some decisions before the realization of uncertain parameters and some decisions after their realization (i.e., first- and second-stage decisions, respectively, in the case of two-stage models). This idea is generally absent in robust optimization as its models try to obtain one solution immune to all possible perturbations of uncertain parameters. A relatively new research area in robust optimization is adjustable robust optimization, which allows modification of some decision variables after some time (a recent survey paper is available from here).
  2. Stochastic programming models require knowledge about probability distribution functions of uncertain parameters. However, robust optimization models do not require such knowledge. So this situation could be used as an indication of which methodology should you use (please note the concepts of expectation and variation could not be defined without such knowledge).

Regarding your second question, scenarios used in stochastic programming or robust optimization usually comes from three sources, namely experts' opinions, historical logs of the system states over the time, or sampling of probability distribution functions governing the uncertain parameters. I think the first two could be used with both stochastic programming and robust optimization. Regarding the third option, you should note that using scenarios is an option to overcome the modeling and solution complexities arising from using discrete or continuous probability functions (e.g., making objective functions and/or feasible region non-convex, non-differentiable, and discontinuous). Other than increasing the number of decision variables and constraints, using scenarios would not result in increasing the complexity of the original deterministic model. In addition, it has been shown that stochastic programming models constructed using scenarios could become good approximations of the original stochastic programming models with discrete or continuous probability functions (see section 3.1.c of "Introduction to Stochastic Programming" by Birge and Louveaux for a discussion).

$\endgroup$
12
$\begingroup$

In reference to the first question, I think it often comes down to the information you have about the underlying uncertainty. If you only have intervals or ranges, robust is the way to go. If you have all of the distributional information (or assume it), stochastic programming is an option. As @TheSimpliFire mentioned, you can include risk measures in stochastic programming formulations to consider risk.

As a note, another option that's becoming more popular is distributionally-robust optimization [1]. The information required is in between robust optimization and stochastic programming. Here, you consider an "ambiguity set" of all of the possible distributions your data could be and optimize your objective hedging against the worst-case distribution.


Reference

[1] Delage E, Ye Y (2010) Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems. Oper. Res. 58(3):595–612.

$\endgroup$
10
$\begingroup$

The following papers discuss this extensively with numerical experiments, but they tackle specific examples. Emphasis is mine.

Kazamzadeh et al. (2017)

This is a comparison of the two techniques using the example of unit commitment, answering your first question.

A popular impression has arisen that the robust approach, with its focus on the worst case, is better able to control risk while stochastic programming emphasizes expected values. However, the stochastic programming formulation can easily accommodate a risk measure. Moreover, the results of both methods depend strongly on the model for the uncertain parameters—either the uncertainty set or the probabilistic scenarios employed in the optimization. [...]

[...] By incorporating risk in the stochastic programming formulation in terms of CVaR with a sufficiently low tail probability, the stochastic programming formulation can achieve the most efficient combinations of cost and risk when a decision maker emphasizes cost. However, when a higher level of conservatism is preferred, robust optimization models can achieve the most efficient combinations of cost and risk. Between the two uncertainty set formulations for robust optimization, the data-driven method that incorporates probabilities of scenarios as well as their ranges of values achieves better cost-risk trade-offs than the one based on ranges alone when the risk parameter is set to its most stringent value.

Maggioni et al. (2014)

This is a comparison of the two techniques using the example of a standard transportation problem. This answers the reverse of your first question (i.e. robust optimisation in favour of stochastic programming) which you may find useful. From the abstract,

The proposed robust formulations have the advantage to be solvable in polynomial time and to have theoretical guarantees for the quality of their solutions, which is not the case for the stochastic formulation. Numerical experiments show that the robust approach results in larger objective function values than the stochastic approach due to the certitude of constraints satisfaction and more conservative decision strategies on the number of booked vehicles. Conversely, the computational complexity is higher for the stochastic approach.


References

[1] Kazamzadeh, N., Ryan, S. M., Hamzeei, M. (2017). Robust optimization vs. stochastic programming incorporating risk measures for unit commitment with uncertain variable renewable generation. Energy Syst. 10:517-541.

[2] Maggioni, F., Potra, F. A., Bertocchi, M. (2014). Stochastic versus Robust Optimization for a Transportation Problem. Available from: http://www.optimization-online.org/DB_FILE/2015/03/4805.pdf. [Accessed 13 August 2019].

$\endgroup$
  • $\begingroup$ Thank you for your complete answer it helped a lot ! $\endgroup$ – Mehdi Aug 14 at 8:59
1
$\begingroup$

Stochastic Optimization (SO) requires the probability distributions (PDF) of the uncertain variables which are usually hard to fit. Then, a large number of scenarios are required to be sampled from these PDFs with their probabilities. This makes some computational complexities and intractability so, scenario reductions are needed but some information will be lost (trade-off). But generally, SO gives acceptable solutions with reduced costs (when you minimize the cost).

On the other hand, Robust Optimization (RO) requires only upper/lower limits of the uncertain variables (simpler than PDFs) but it optimizes over the worst-case scenario which usually has low probability (with higher cost value). So RO gives more conservative solutions with lower computations but with higher costs.

I think using SO is preferred when you concern more about cost function value but RO is useful when reliability and security are more important than cost.

New contributor
shady mamdouh is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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