A New Robust Scenario Approach to Supply Chain Optimization Under Uncertainty

A new robust scenario approach to supply chain optimization under uncertainty

Niaz Chowdhury, Xiang Li*

Department of Chemical Engineering, Queen's University,

19 Division Street, Kingston, ON, K7L 3N6, Canada

The following two-stage stochastic programming models [1] are often used for supply chain optimization under uncertainty:

                                                     (1a)

,                                                                       (1b)

where the first-stage variables are represented by , the second stage cost for uncertainty realization  is represented by,

,

where , , , ,  are known constants. This two-stage model is often approximated by the following scenario formulation for tractable solution  [1]:

                                                             (2a)

                                                                                           (2b)

     ,        (2c)

where  are sampled uncertainty realizations, called scenarios, and  are the probabilities associated with the scenarios. The major shortcoming of the scenario formulation is that, a large number of scenarios are usually needed, to ensure that the solution is feasible for the original two-stage formulation and that the predicted expected cost is close to the true expected cost. To overcome the shortcoming of the scenario formulation, a robust scenario formulation has been proposed [2-3] based on partitioning the uncertainty region  rather than sampling a finite number of uncertainty realizations from it. The resulting formulation is

                                   (3a)

                                                                                  (3b)

    (3c)

where scenario  is associated with uncertainty subregion  rather than a uncertainty realization and  is required to ensure that the solution to Formulation (3) is feasible for the original problem. The second stage decision for scenario  is assumed to be an affine function of the uncertainty realization in , i.e., . As a result, the coefficients of the affine function ( ) rather than  serve as the second-stage variables in the optimization problem.

The construction of uncertainty subregions and the reformulation of Formulation (3) into a tractable deterministic optimization problem are the two key steps for applying the robust scenario method. In previous work [2-3], the uncertainty region bounded by the infinity-norm (i.e., box uncertainty) is considered, for which the construction of uncertainty subregions is straightforward (see Figure 1(a)). In addition, in this case the uncertainty subregions are also bounded by the infinity-norm, so Formulation (3) can be equivalently transformed into a deterministic linear programming problem. However, when the original uncertainty region has an arbitrary shape, it is not clear how to effectively partition the region to yield a set of uncertainty subregions such that Formulation (3) can be transformed into a tractable deterministic optimization problem (see Figure 1(b)).

Figure 1. Partition of uncertainty regions.

In this paper, we propose a novel robust scenario approach that constructs a sequence of box uncertainty subregions that over-estimate the original uncertainty region, and a sequence of box uncertainty subregions that under-estimate the original uncertainty region (as illustrated in Figure 2). The robust scenario formulations with the over- and under-estimation of uncertainty region can both be transformed into deterministic linear programming problems; when the number of scenarios (i.e., uncertainty subregions) increase, the over- and under-estimates of the uncertainty region become close and the optimal values of the two robust scenario formulations converge, leading to a good solution for the original two-stage stochastic programming problem. Case study of a real industrial supply chain optimization problem with ellipsoidal demand uncertainty demonstrates the advantages of the proposed robust scenario approach.

Figure 2. Over- and under-estimation of uncertainty region

References

[1] Birge, J. R.; Louveaux, F. Introduction to stochastic programming, Second Edition; Springer: New York, 2011.

[2] McLean, K.; Li, X. "Robust scenario formulations for strategic supply chain optimization under uncertainty", Industrial & Engineering Chemistry Research, 52, 5721-5734.

[3] McLean, K.; Ogbe, E.; Li, X. "Novel formulation and efficient solution strategy for strategic optimization of an industrial chemical supply chain under demand uncertainty", Canadian Journal of Chemical Engineering, DOI 10.1002/cjce.22173, 2015.