I have a two-stage stochastic programming problem in which the expected-value solution results in a quite different first-stage solution than the recourse problem. Although the value of VSS (defined below) is often positive, it is somewhat negligible.

The Value of Stochastic Solution (VSS) is defined as the difference between the Expectation of the Expected Value Solution (EEVS) and the optimal objective value of the Recourse Problem (RP).

This definition only considers the objective function values to determine the merits of the stochastic solution. I think this is not a good index in the sense that it does not consider the structure of the solutions. I was wondering if there are any other index for evaluating the merits of a stochastic problem in comparison to the expected value problem? I feel that this has already been studied in the literature, but I could not find a reference.

EDIT: It should mention that the stochastic program with a large number of scenarios can be solved efficiently, so I am not looking for a way to speedup solving the SP by reducing the number of first-stage variables or by reducing the number of scenarios. I just want a measure to quantify the value of stochastic solution. I thought maybe this has something to do with robustness or robust optimization, but RO is a different field.


1 Answer 1


In the paper by Crainic et al.1, the authors stated that "Focusing on two-stage formulations, we show how and under which conditions the reduced costs associated to the variables in the deterministic formulation can be used as an indicator for excluding/retaining decision variables in the stochastic model. We introduce a new measure, the Loss of Reduced Costs-based Variable Fixing (LRCVF), computed as the difference between the optimal values of the stochastic problem and its reduced version obtained by fixing a certain number of variables.

Maggioni et al.2 proposed the concepts of the Value of the Right Distribution (VRD), the Performance Bound (PB) and the Worst-Case Performance Bound (WPB), which can be applied to quantify how much the lost will be if we guess the wrong distribution of the uncertain parameters affecting a stochastic optimization problem. They applied these concepts in two-stage stochastic programming model of the cost-based variant of the classical Newsvendor problem.

I think above-mentioned papers can give you a good start point in searching for alternative indexes for VSS.

[1] Crainic, Teodor G., et al. "Reduced cost-based variable fixing in two-stage stochastic programming." Annals of Operations Research (2018): 1-37.

[2] Maggioni, Francesca, Matteo Cagnolari, and Luca Bertazzi. "The value of the right distribution in stochastic programming with application to a Newsvendor problem." Computational Management Science (2019): 1-20.

  • 6
    $\begingroup$ Formatting tip: Note that writing <sup>1</sup> yields a superscript 1 instead of resorting to MathJax. $\endgroup$ Aug 28, 2019 at 6:01

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.