On Multistage Stochastic Mixed 0–1 Optimization with Time-Consistent Stochastic Dominance Risk Averse Management

Abstract

A new time-consistent risk averse measure is considered, so-called Expected Conditional Stochastic Dominance (ECSD), for multistage stochastic mixed 0–1 optimization, where first- and second-order stochastic dominance risk averse functionals are taken into account. As a result of the ECSD modeling, its problem solving is much more difficult than the Risk Neutral counterpart, so, it is unrealistic to solve the problem up to optimality by plain use of MIP solvers. Instead of it, decomposition algorithms of some type should be used. Computational results are reported for instances of a well-known real-life problem, where a decomposition matheuristic algorithm is tested in its efficiency and computing effort, having the plain use of a MIP solver as a benchmark for computational purposes.

1 Introduction

Stochastic optimization is currently one of the most robust tools for decision making. It is broadly used in real-world applications in a wide range of problems from different areas in energy, finance, production, distribution, supply chain management, etc. The continuous optimization problems under uncertainty have been studied in [4] for risk neutral (RN) problems, and [16] for risk averse measures, among others. A survey on exact and inexact decomposition algorithms is performed in [9]. It is well known that an optimization (say, minimization) mixed 0–1 problem under uncertainty with a finite number of possible supporting scenarios has a mixed 0–1 Deterministic Equivalent Model (DEM). Traditionally, special attention has been given to optimizing the DEM by minimizing the objective function expected value in the scenarios, subject to the satisfaction of all the problem constraints in the defined scenarios, i.e., the so-called risk neutral (RN) approach. Currently, we are able to solve huge DEMs by using different types of decomposition approaches, e.g., see in [1] our last improvement of the Branch-and-Fix Coordination (BFC) methodology. However, the optimization of the RN model has the inconvenience of providing a solution that ignores the potential variability of the objective function value (say, cost) in the scenarios and, so, it does not avoid the potential high negative impact of the proposed solution in the low-probability high-cost scenarios to occur.

However, there are some risk averse approaches that, additionally, deal with risk management, see a good survey in [2], among others. As we know, the first risk averse measure, so-called Chance Constraint (CC) functional, was introduced in the seminal work [5], where the problem’s feasible set is restricted to satisfying an upper bound on the probability (in our case, the expected fraction of scenarios) of having shortfall on satisfying each of the modeler-driven constraints. It is also so-called first-order stochastic dominance (FSD) that for a two-stage setting was introduced in [12], where a Lagrangean-based decomposition algorithm was used for problem solving. Another of the first risk averse measures, so-called Integrated Chance Constraint (ICC) functional, was introduced in [14] and expanded in [15]. The ICC type 1 is also so-called second-order stochastic dominance (SSD) that for a two-stage setting was introduced in [11], where a Lagrangean-based decomposition algorithm was used for problem solving. The multistage risk averse time-inconsistent measure based on the SSD functional was introduced in [6] for a set of profiles related to given thresholds on a multifunction setting (including the objective function). As an extension of the two-stage SD mixed-integer linear recourse, FSD and SSD measures were jointly used in a multistage mixed 0–1 setting, so-called Time Stochastic Dominance (TSD), see our works [7, 9], where the decomposition algorithms use scenario clustering in the BFC scheme in the first work and a Lagrangean-based scheme in the other one.

The risk averse functional subject of this work, so-called Expected Conditional Stochastic Dominance (ECSD), is a time-consistent risk averse functional, since it bounds the scenario probability of having shortfall on satisfying different rhs for given constraints, and it also bounds the expected shortfall, both for the scenario groups with a one-to-one correspondence with nodes in the scenario tree related to a chosen set of stages in the time horizon. Roughly, a risk averse measure is time-consistent if the solution at any node in the scenario tree does not depend on the scenarios that cannot occur at that node. Obviously, RN is a time-consistent measure. Some other time-consistent measures, mainly the Expected Conditional Value-at-Risk, have been studied in [3, 13], among others.

The rest of the paper is organized as follows. For completeness and notation presentation, Sect. 2 deals with the main concepts of risk neutral-based mathematical optimization under uncertainty. Section 3 deals with the risk averse measure ECSD. Section 4 reports some results of our computational experiment. Section 5 concludes.

2 Risk Neutral Measure in Multistage Mixed 0–1 Stochastic Problems

The DEM, compact representation, of the multistage mixed 0–1 model for minimizing the objective function expected value in the scenarios (i.e., a RN approach) can be expressed

$$\begin{aligned} \begin{array}{lll} &{} z_{RN} = \min \, \displaystyle \sum _{g\in \mathscr {G}}w_g(a_g x_g + b_g y_g) \\ &{} \text {s.t.} ~ \displaystyle \sum _{q\in \mathscr {A}_g} (A^g_q x_q + B^g_q y_q) = h_g &{} \forall g\in \mathscr {G} \\ &{} x_g\in \{0,1\}^{nx(g)}, ~~ y_g\in \mathbb {R}^{ny(g)} &{} \forall g\in \mathscr {G}, \end{array} \end{aligned}$$

(1)

where $\mathscr {G}$ is the set of nodes in the scenario tree, $w_g$ is the weight computed for node $g\in \mathscr {G}$, such that $w_g = \sum _{\omega \in \varOmega _g}w_\omega$, where $w_\omega$ is the modeler-driven probability of scenario $\omega$, for $\omega \in \varOmega$, where $\varOmega$ is the finite set of scenarios considered in the supporting tree; $x_g$ and $y_g$ are the nx(g) and ny(g)-dimensioned vectors of the 0–1 variables and the continuous variables, resp., for node $g\in \mathscr {G}$; $a_g$ and $b_g$ are the vectors of the objective function coefficients for $x_g$ and $y_g$, resp.; $\mathscr {A}_g$ is the set included by the same node g and its ancestors in the scenario tree with nonzero coefficients in the constraints of node $g\in \mathscr {G}$; $A_q^g$ and $B_q^g$ are the constraint matrices; and $h_g$ is the rhs for node $g\in \mathscr {G}$. All vectors and matrices are with the adequate dimensions. Notice that the non-anticipativity constraints (NAC) are implicitly satisfied.

Additionally, let the following notation to be used throughout this work. $\mathscr {T}$ is the set of stages $\{1,2,\dots ,T\}$ in the time horizon with $T=|\mathscr {T}|$; $\mathscr {G}_t \subseteq \mathscr {G}$ is the set of nodes in stage $t\in \mathscr {T}$, where $|\mathscr {G} _1|=1$. Let $\varOmega _g \subset \varOmega$ be the set of scenarios in group g, where it has a one-to-one correspondence with node g in the scenario tree, for $g\in \mathscr {G}$; for easing notation, let $\omega \equiv g$ for $g\in \mathscr {G}_T$ and, then, $\omega \in \varOmega _g$, where $|\varOmega _g|=1$; t(g) is the stage to which node g belongs to, such that $g\in \mathscr {G}_{t(g)}$; $\tilde{\mathscr {A}}_g$ is the set of ancestor nodes in the scenario tree to node g (including itself), for $g\in \mathscr {G}$ (such that $\mathscr {A}_g\subseteq \tilde{\mathscr {A}}_g$); and $\tilde{\mathscr {S}}_g$ is the set included by the same node g and its successors in the scenario tree, for $g\in \mathscr {G} \setminus \mathscr {G}_T$.

3 ECSD Risk Averse Measure in Multistage Mixed 0–1 Stochastic Problems

The RN model (1) aims to minimize the objective function expected value alone subject to the constraint system in the model. As stated above the main criticism that can be made to this very popular strategy is that it ignores the variability of the objective function value in the scenarios and, in particular, the “right” tail of the non-wanted scenarios. The Expected Conditional Stochastic Dominance (ECSD) risk averse measure also minimizes the objective function expected value but, besides the set of RN constraints, a set of profiles is considered for a set of functions (including the objective one) in a given scenario subset. Each profile is included by a threshold on the function value for any scenario that belong to a given group (to be defined below) up to the end of the time horizon, a bound target on the fraction of those scenarios having excess on reaching it (the so-called first-order ECSD), a bound target on the expected excess (the so-called second-order ECSD) and a bound target on the excess for any of those scenarios. Observe that the type of risk reduction functional that is considered in this work also allows other functions besides the objective one, such as environmental functions in industrial strategic investment, mitigation effects of natural disasters, and preservation of cultural, monumental and strategic assets, among others; all of them can be accommodated in the framework presented below.

So, let the additional notation, $\mathscr {F}$ is the set of indexes of the risk reduction oriented functions to consider, such that $a_g^f$ and $b_g^f$ are the vectors of the coefficients of the variables in $x_g$ and $y_g$ for $g\in \mathscr {G}$ in the function indexed with f, for $f\in \mathscr {F}$. Let us consider that $f=1$ is the index for the objective function and, so, $a_g^1 \equiv a_g$ and $b_g^1 \equiv b_g$. Let also $\tilde{\mathscr {T}}^f \subseteq \mathscr {T}\setminus \{T\}$ be the modeler-driven stage set for function $f\in \mathscr {F}$, such that the risk reduction measure ECSD is performed for each group of scenarios $\varOmega _g$, for $g\in \mathscr {G}_t, \, t\in \tilde{\mathscr {T}}^f$. Let also $\mathscr {P}_g^f$ denote the set of indexes of the related profiles for the function indexed with $f\in \mathscr {F}$ and the scenarios in set $\varOmega _g$, for $g\in \mathscr {G}_t, \, t\in \tilde{\mathscr {T}}^f$, such that the profile indexed with p, for $p\in \mathscr {P}_g^f$, is included by the 4-tuple $(\phi ^p, \, \tilde{e}^p, \, \overline{e}^p, \, \overline{\nu }^p)$, where,

$\phi ^p$,:

threshold for the value of function f up to the last stage T in the time horizon in scenario $\omega$, for $\omega \in \varOmega _g$.

$\tilde{e}^p$,:

bound target on the excess of any of those scenarios on reaching the threshold.

$\overline{e}^p$,:

bound target on the expected excess.

$\overline{\nu }^p$,:

bound target on the expected fraction of those scenarios with excess.

Let the following additional variables for scenario $\omega$ and profile p, for $\omega \in \varOmega _g, \, p\in \mathscr {P}_g^f, \, g\in \mathscr {G}_t, \, t\in \tilde{\mathscr {T}}^f, \, f\in \mathscr {F}$:

$e_\omega ^p$ :

, continuous variable that takes the excess of the value of function f on reaching threshold $\phi ^p$, for scenario $\omega$.

$\nu _\omega ^p$ :

, 0–1 variable that takes the value 1 if the value of function f has an excess on reaching threshold $\phi ^p$ and otherwise, 0, for scenario $\omega$.

The ECSD model can be expressed

$$\begin{aligned} \begin{array}{lll} &{} z_{ECSD} = \min \, \displaystyle \sum _{g\in \mathscr {G} }w_g(a_g^1 x_g + b_g^1 y_g) &{}\\ &{} + \displaystyle \sum _{f\in \mathscr {F}}\sum _{t\in \tilde{\mathscr {T}}^f}\sum _{g\in \mathscr {G}_t}\sum _{p\in \mathscr {P}_g^f}\bigl (M_{\epsilon _{\tilde{e}^p}} \epsilon _{\tilde{e}^p} + M_{\epsilon _{\overline{e}^p}} \epsilon _{\overline{e}^p} + M_{\epsilon _{\overline{\nu }^p}} \epsilon _{\overline{\nu }^p} \bigr ) &{} \\ &{} \text {s.t.} ~ \displaystyle \sum _{q\in \tilde{\mathscr {A}}_g} (A_q^g x_q+ B_q^g y_q) = h_g &{} \forall g\in \mathscr {G}\\ &{} x_g\in \{0,1\}^{nx(g)}, ~~ y_g\in \mathbb {R}^{ny(g)} &{} \forall g\in \mathscr {G} \\ \\ &{} \displaystyle \sum _{g\in \tilde{\mathscr {A}}_\omega } (a_q^f x_q + b_q^f y_q) - e_\omega ^p \le \phi ^p &{} \forall \omega \in \varOmega _g, ~ p\in \mathscr {P}_g^f, ~ g\in \mathscr {G}_t, ~ t\in \tilde{\mathscr {T}}^f, ~ f\in \mathscr {F} \\ \\ &{} 0 \le e_\omega ^p \le \tilde{e}^p \nu _\omega ^p + \epsilon _{\tilde{e}^p}, \,\, &{} \end{array} \end{aligned}$$

$$\begin{aligned} \begin{array}{lll} &{} \nu _\omega ^p\in \{0,1\}, \,\, \epsilon _{\tilde{e}^p}\in \mathbb {R}^+ &{} \forall \omega \in \varOmega _g, ~ p\in \mathscr {P}_g^f, ~ g\in \mathscr {G}_t, ~ t\in \tilde{\mathscr {T}}^f, ~ f\in \mathscr {F}\\ \\ &{} \displaystyle \sum _{\omega \in \varOmega _g}w_\omega e_\omega ^p \le \overline{e}^p + \epsilon _{\overline{e}^p}, \,\, \epsilon _{\overline{e}^p}\in \mathbb {R}^+ &{} \forall p\in \mathscr {P}_g^f, ~ g\in \mathscr {G}_t, ~ t\in \tilde{\mathscr {T}}^f, ~ f\in \mathscr {F}\\ &{} \displaystyle \sum _{\omega \in \varOmega _g}w_\omega \nu _\omega ^p \le \overline{\nu }^p + \epsilon _{\overline{\nu }^p}, \,\, \epsilon _{\overline{\nu }^p}\in \mathbb {R}^+ &{} \forall p\in \mathscr {P}_ g^f, ~ g\in \mathscr {G}_t, ~ t\in \tilde{\mathscr {T}}^f, ~ f\in \mathscr {F}, \end{array} \end{aligned}$$

(2)

where the last terms in the objective function prevent the potential infeasibility of the risk averse constraint system, such that the big M-parameters are the related penalization and the $\epsilon$-variables are the slack ones to avoid the infeasibility.

The concept of expected conditional risk avere measure (ECRM) is introduced in [13], and its time-consistency is defined and proved. We show elsewhere [10] that ECSD is a member of the family of ECRMs and, therefore, it is time consistent. Let us assume that the decisions in a given problem have been made up to node g, for $g\in \cup _{\{t\in \mathscr {T}:t <T\}}\mathscr {G}_t$, according to the solution obtained in the original model (2) solved at stage $t=1$. Now, let the submodel solved at node g, such that it is supported by the subtree rooted with node g whose successor nodes are in set $\tilde{S}_g$. Then, the rationale behind a time-consistent risk averse measure is that the solution value to be obtained in the submodel solved at stage t(g) for node g should have the same value as in the original model solved at stage $t=1$.

4 Some Computational Experience

Let the tactical supply chain planning (TSCP) problem presented in our work [10] to be the pilot case where to consider the performance of the RN and ECSD risk measures. Its deterministic version is based on a real-life case in the assembly sector. TSCP has a broad applicability, specifically, in sectors such as car, computer and domestic appliances manufacturing, among others. It is the case in which a company with multiple raw material suppliers, plants, products, tiers of production in the bill of material (BoM) and markets needs to satisfy a product demand vector over a given time horizon. The goal is to determine a raw material supplying plan and a master production, inventory and distribution planning that best makes use of the available resources and their capacity extension acquisitions in the whole supply chain for each period of a given time horizon. The resources’ best use consists of minimizing the raw material supplying commitment cost, the production and inventory costs in the plants, and the product backlog and demand lost penalization along the time horizon. The raw material supplying commitment cost is frequently modeled by a piecewise linear, concave and nondecreasing function of the total volume to commit for the whole time horizon. Typical types of constraints (some of them related to either-or decisions) are as follows: Balance equations of end-products and components, conditional lower and upper bounds for raw material supplying and product release, resource consumption bounds and capacity extension acquisitions, and balance equations of lost demand and backlogging, among others. There are different types of resources at different levels for groups of consecutive periods (so-called stages) along the time horizon. The cost of the resources’ capacity extension acquisition is expressed as a piecewise discrete and nondecreasing function. Another important feature of the problem is that the burden of raw material stocking is frequently transferred to the suppliers.

The experiment was conducted on a PC with a 2.5 GHz dual-core Intel Core i5 processor, 8 Gb of RAM and the operating system was OS X 10.9, where the MIP solver to use is CPLEX v12.5 and its optimality tolerance is set up to 0.001. The decomposition algorithm to use is our matheuristic SDP-ECSD [10].

The problem’s dimensions of the testbed under consideration are up to 9 stages, 20 end-products, 30 market centers each, 20 subassemblies, 40 raw materials, and 25 types of resources. Table 1 presents the structure of the scenario tree for each instance as well as the dimensions of the two stochastic formulations. The set of stages $\mathscr {T}$ has been split in two parts for problem solving. The first column of the table is the identifier of the instance, and the second one gives the predefined structure $A_{1}^{B_1} A_{2}^{B_2}$ of the scenario tree, where $A_i$ denotes the number of children that each node has in each stage in part i, and $B_i$ is the number of its stages, for $i=1,2$. The period subset $\tilde{\mathscr {T}}$ is singleton and $t^*\in \tilde{\mathscr {T}}$, where $t^*$ is the period defining the groups of scenarios for cost risk reduction in the ECSD measure. The headings of the columns for the dimensions of the models are as follows: nc, number of continuous variables; n01, number of 0–1 variables; and m, number of constraints.

Table 1 STSCP Models’ dimensions

Table 2 RN model (1) solved with CPLEX and the SDP-ECSD matheuristic

The results of solving RN model (1) are shown in Table 2. The first column refers again to the identifier of the instance. The following three columns reports the CPLEX results, where $\overline{z}_{CPX}$ is the RN cost value, $t_{CPX}$ is the elapsed time (in seconds) to obtain it, and OG% is its optimality gap (in %). The optimization of the instances reaches the allowed time (2h) without proving the 0.1%-optimality of the solution. Another block of columns in Table 2 reports the SDP-ECSD results. The headings are as follows: $\overline{z}_{RN}$ and $t_{RN}$, RN solution value and related elapsed time (in seconds); and GG%, goodness gap, i.e., the deviation of the solution value obtained by the matheuristic from the value obtained by CPLEX, expressed as $GG\%=(\overline{z}_{RN} -\overline{z}_{CPX})/\overline{z}_{CPX}$%. We can observe that, generally, the elapsed time that is required by SDP-ECSD is very small. On the other hand, the goodness gap of its RN value versus the one provided by CPLEX is very small as well; notice that it goes form 1.09 to 1.39%.

The violations of the $\overline{e}_{RN}^p$ and $\overline{\nu }_{RN}^p$ ECSD bounds for $p=1,2$ by the RN solution are up to 165 and 700%, respectively. The details are not shown but they are available from the authors under request, see also [10].

The results of solving ECSD model (2) by matheuristic SDP-ECSD are shown in Table 3. Some headings are as follows: $\overline{z}_{ECSD}$ and $t_{ECSD}$, ESCD incumbent value and related elapsed time (in seconds); and $dev_{ECSD}$%, deviation of the ESCD cost from the RN one (see Table 2), expressed as $dev_{ECSD}\%=(\overline{z}_{ECSD}-\overline{z}_{RN})/\overline{z}_{RN}\%$.

Table 3 ECSD model (2) solved with the SDP-ECSD matheuristic

Notice that the elapsed time required by the matheuristic for solving the ECSD model (2) is much greater than the time required for solving the RN model (1). It confirms the common knowledge, namely, the stochastic dominance strategy are computationally much harder than the RN one (requiring an elapsed time that is one order of magnitude higher than the time required for obtaining the RN solution). It is due to the cross scenario constraints for satisfying the risk reduction measure. Notice that, probably, CPLEX could not even solve the ECSD model, since it could not do it for the RN one. On the other hand, the deviation of the ECSD cost (due to the satisfaction of the cost risk reduction constraint system) could even reach the increment of the 14.04% of the RN cost (where, as notice above, the violations of the two types of risk reduction bounds are up to 165 and 700%).

5 Conclusions

Frequently there are problems with high variability in the functions to consider (beside the one to minimize). So, a risk reduction functional is required for avoiding low-probability high-negative function values incurred by the solutions obtained from the minimization of the objective function expected (cost) value. In this work we have considered the time-consistent multi-function first- and second-order stochastic dominance functional ECSD for risk management to control. It allows to personalize the type of risk reduction profiles for groups of scenarios. That high risk management could increase the cost function value while satisfying the risk reduction constraint system. Any way, a specialization of decomposition algorithms is required for problem solving in a affordable computing effort. We have used our SDP-ECSD decomposition algorithm for problem solving in a pilot case from the tactical supply chain field; the solution’s quality is good enough and the computing effort is very affordable.