1 Introduction

Uncertainty is an important aspect of every decision-making process and has been extensively studied in optimization literature. Therefore, it is surprising that a large disconnect still remains between state-of-the-art advancements and practical applications uncertainty management technology in industrial systems.

Excellent reviews on the topic of optimization under uncertainty have been published by Sahinidis (2004) and Li and Ierapetritou (2008). As noted by Sahinidis (2004), one of the opportunities for this topic is the “need for systematic comparisons between the different modeling philosophies”. In addition, Li and Ierapetritou (2008) mention the need for “extended work in the direction of more effective and general method for dealing with the uncertainties in process industry”.

This paper provides a context for methodologies currently applied to optimization problems under uncertainty so that new users have a better understanding of the field as a whole. Therefore, we propose categories for the different types of decisions that are commonly made in the process industries from a user’s perspective. This contrasts with the usual approach in the literature of mapping optimization methods to practical applications. For each of the proposed categories, we indicate appropriate optimization methods and additional references.

Uncertainty affects industrial processes in different ways. Given the existence of uncertainty in model parameters, the user may choose to take one or more of the following steps:

  1. 1.

    Make decisions with the best available estimate of uncertain parameters (Acquisition, deterministic optimization)

  2. 2.

    Determine how uncertainty affects decisions (Assessment)

  3. 3.

    Make decisions that account for uncertainty (Adjustment)

  4. 4.

    Reduce parametric uncertainty in order to lessen its effect on decisions (Abatement)

Uncertainty may be introduced in a decision-making system either through modeled relationships between its variables (also called “structural uncertainty”) or through uncertainty in model parameters, such as material pricing and availability information, product yield information. This paper focuses on “parametric uncertainty”, i.e., uncertainties in model parameters.

To being with, it is very important to highlight the difference between exogenous and endogenous sources of uncertainty. The former originates from the environment, such as arrival times of raw materials. In optimization problems, it may manifest itself as uncertainty in objective function, right-hand side and/or left-hand side model coefficients. Endogenous sources of uncertainty, on the other hand, arise from the nature of decision-making processes, such as when decisions are required before information about all parameters becomes fully available. This situation is very common in dynamic decision-making systems, resulting in two or more different sets of decision variables. In Operations Research literature, these sets are usually referred to here-and-now (HAN) and wait-and-see (WAS) variables.

Decisions represented by HAN variables have to be made before the values of all parameters are available. This is the case in planning and scheduling problems, where “immediate” decisions (e.g., the first day for a scheduling problem, or the first month for a planning problem) are made before all customer demands and raw material supply amounts are known for the full decision-making horizon (e.g., a week or a semester, respectively).

Conversely, WAS decisions can be made after information about the parameter values becomes available. This is the case of backcasting problems, where “perfect” decisions for the plan or schedule are calculated after all of the actual parameter outcomes in the system are known. For this reason, backcasting is often used as a benchmark for the decisions that have been actually implemented in the system.

The following sections in this paper address the different steps the user may take when dealing with an uncertain system. Section 2 guides the user through different Uncertainty Assessment goals and techniques. The assessment may concern the feasibility of the uncertain system (i.e., whether the decision will still be feasible for any parameter realization) or the objective function value (i.e., evaluating what the decision would have been had the uncertain parameter outcomes been known at the time of decision-making).

Section 3 presents Uncertainty Adjustment methods, which adjust decisions in order to reduce the impact of uncertainty. Similarly to assessment techniques, the adjustment of decisions can also be made aiming at maintaining system feasibility or at mitigating the effects of objective function value.

In Sect. 4 some Uncertainty Abatement methods are discussed. These techniques reduce parameter uncertainty before it affects the decision-making system.

It is important to note that many of the methods described in Sects. 2, 3, and 4 are computationally intensive. To this purpose, Sect. 5 presents solution simplification approaches, both continuous and discrete. In addition, since scenario-based methods are often used in industry, a more detailed discussion regarding their generation, comparison, assessment and management is also included in this section. An outline of this paper’s structure can be seen in Fig. 1.

Fig. 1
figure 1

Outline of uncertainty-related topics

Full size image

To illustrate the management of uncertain systems, a crude oil blending example from Kelly and Mann (2003) will be used throughout this paper (Fig. 2).

Fig. 2
figure 2

Crude oil blending example

Full size image

In Fig. 2, different types of crude oil arrive by pipeline and are sent to two holding tanks, T1 for light crude oils and T2 for heavy crude oils. The material is allowed to settle for a minimum of 9 h before being blended into the material that can be processed by the refinery through the transfer line. The crude oil blends are stored for a minimum of 3 h in charging tanks T3 and T4. The blended crude oils must satisfy quality specifications, such as specific gravity and sulphur. This example will be used to give a practical context to several techniques described in the remaining sections of this paper.

2 Assessment: determining the impact of uncertainty

The first step to managing uncertainty in a system should be to assess its impact on the decisions. If uncertainty does not affect decisions in a significant way, no further action is required.

The next subsections describe methods that can be used to assess the impact of uncertainty on the overall feasibility of the optimization problem and on its objective function value.

2.1 Impact on feasibility

In some systems, it is important to know whether the HAN decisions that are made will still be feasible for all possible future parameter realizations. In planning and scheduling problems, guaranteeing overall feasibility implies that the plan or schedule will still be implementable for any parameter outcome.

In addition to information regarding feasibility of the current decision, the user may also wish to know the allowable ranges of parameter variation that will not modify this decision. In this context, a decision-making problem is not considered to be very sensitive if parameter ranges are very wide.

2.1.1 Impact of exogenous uncertainty on constraint feasibility

In order to determine the impact of uncertainty on feasibility, the following question must be addressed: “Given the range of parameter variation, is the optimal decision x* still feasible (valid)?”. In the context of the example in Fig. 2, the decision-maker might be interested in assessing the feasibility of a certain schedule given a range of possible incoming crude oil properties (e.g., sulphur).

The problem posed above may be solved by applying the feasibility test (Halemane and Grossmann 1983; Swaney and Grossmann 1985a, b; Grossmann and Floudas 1987), expressed as follows:

Problem (1):

$$ \chi \left( {x^{*} } \right) = \mathop {Maximize}\limits_{\theta } \phi $$

Subject to

$$ \theta^{LB} \le \theta \le \theta^{UB} $$
$$ \phi = \mathop {Minimize}\limits_{{y_{in} }} \sum\limits_{in} {y_{in} } $$

Subject to

$$ g_{in} \left( {y_{in} ,\theta } \right) = A_{in} \left( \theta \right) \cdot x^{*} - b_{in} \left( \theta \right) - y_{in} \ge 0 $$
$$ g_{LB,in} \left( {y_{in} } \right) = y_{in} \ge 0 $$

In Problem (1), the goal is to maximize the minimum sum of slack variables y over all parameter values given a fixed set of decision variables x *. Equality constraints can be included by using two slack variables for each equality constraint. If φ ≤ 0 at the solution of Problem (1), the decision x * is feasible for any outcome of parameters θ.

Problem (1) is a bilevel optimization problem. One of the methods used to solve this problem is to replace the inner optimization problem φ with its Karush–Kuhn–Tucker (KKT) optimality conditions, yielding the following reformulated problem (Grossmann and Floudas 1987):

Problem (2):

$$ \chi \left( {x^{*} } \right) = \mathop {Maximize}\limits_{\theta } \phi $$

Subject to

$$ \theta^{LB} \le \theta \le \theta^{UB} $$
$$ g_{in} \left( {y_{in} ,\theta } \right) = A_{in} \left( \theta \right) \cdot x^{*} - b_{in} \left( \theta \right) - y_{in} \ge 0 $$
$$ g_{LB,in} \left( {y_{in} } \right) = y_{in} \ge 0 $$
$$ 1 + \lambda_{in} - \lambda_{LB,in} = 0 $$
$$ g_{in} \left( {y_{in} ,\theta } \right) \cdot \lambda_{in} = 0 $$
$$ g_{LB,in} \left( {y_{in} } \right) \cdot \lambda_{LB,in} = 0 $$

This reformulation results in a non-convex nonlinear programming problem due to the existence of complementarity constraints (constraints of the form g·λ = 0). Consequently, if solving Problem (2) with a standard nonlinear solver, the solution may lie at a local optimum value. Alternatively, the complementarity constraints can be reformulated as MILP, allowing Problem (2) to be solved to provable optimality. In the following equations, M is a large positive number (Grossmann and Floudas 1987):

$$ g_{in} \left( {y_{in} ,\theta } \right) \le M \cdot \left( {1 - \delta_{in} } \right) $$
$$ \lambda_{in} \le M \cdot \delta_{in} $$
$$ g_{LB,in} \left( {y_{in} } \right) \le M \cdot \left( {1 - \delta_{LB,in} } \right) $$
$$ \lambda_{LB,in} \le M \cdot \delta_{LB,in} $$

The feasibility test allows a continuous distribution of parameters to be considered albeit with potentially high computational costs associated with solving either a non-convex NLP or a MILP. For the sake of concision, in the remainder of this paper only the NLP formulation of complementarity constraints will be shown, even though the MILP reformulation always holds for these types of constraints.

Instead of reformulating Problem (1) using KKT conditions, a scenario-based approach can be used. It is important to note that the problem size when using scenario-based methods increases greatly with the number of uncertain parameters and can also become intractable. A more detailed discussion on the use of scenario-based approaches is presented in Sect. 5.

When using scenarios, several linear programs need to be solved using the following reformulation: Problem (3):

$$ \chi \left( {x^{*} } \right) = \mathop {Maximize}\limits_{{\theta_{s} }} \, \varphi $$

Subject to

$$ \phi = \mathop {Minimize}\limits_{{y_{in} }} \sum\limits_{in} {y_{in} } $$

Subject to

$$ g_{in} \left( {y_{in} ,\theta_{s} } \right) = A_{in} \left( {\theta_{s} } \right) \cdot x^{*} - b_{in} \left( {\theta_{s} } \right) - y_{in} \ge 0 $$
$$ g_{LB,in} \left( {y_{in} } \right) = y_{in} \ge 0 $$

Sub-problem φ is solved as many times as there are scenarios. In this case, parallel processing is a good option to reduce overall computation times, since the sub-problems can be processed independently. If any scenario s yields φ > 0 (i.e., a non-zero penalty value), this indicates that the parameter values θs will not allow the optimal decisions x * to be feasibly implemented in the system.

2.1.2 Impact of decisions on parameter ranges/"Robustness” of decisions

The previous section focused on evaluating the effect of an uncertainty range on the current decisions x *. In other circumstances, the user may want to obtain the range of parameter outcomes that will not cause the decision x * to be infeasible. This concept is related to the “type I sensitivity” defined by Koltai and Terlaky (2000) which corresponds to the parameter outcomes for which the optimal basis remains the same. The difference between the two interpretations is that, in the former, the user is mainly interested in maintaining feasibility of the problem, whereas in the latter, optimality is also addressed.

In the crude oil blending example (Fig. 2), the decision-maker would be interested in determining the largest possible sulphur variations in incoming crude oils that would not alter his/her original schedule (either in terms of feasibility and/or optimality).

The flexibility index was developed for obtaining parameter ranges that guarantee the feasibility of the optimization problem given a fixed decision x * (Halemane and Grossmann 1983; Swaney and Grossmann 1985a, b; Grossmann and Floudas 1987). The flexibility index f can be calculated as follows:

Problem (4):

$$ F = \mathop {Maximize}\limits_{f} f $$

Subject to

$$ \mathop {Maximize}\limits_{\theta } \phi $$

Subject to

$$ \theta^{N} - f \cdot \Delta \theta \le \theta \le \theta^{N} + f \cdot \Delta \theta $$
$$ \phi \le 0 $$
$$ \phi = \mathop {Minimize}\limits_{{y_{in} }} \sum\limits_{in} {y_{in} } $$

Subject to

$$ g_{in} \left( {y_{in} ,\theta } \right) = A_{in} \left( \theta \right) \cdot x^{*} - b_{in} \left( \theta \right) - y_{in} \ge 0 $$
$$ g_{LB,in} \left( {y_{in} } \right) = y_{in} \ge 0 $$

In Problem (4), the flexibility index f is maximized subject to the feasibility of the underlying optimization problem (implied by the constraint ϕ ≤ 0).

Problem (4) is a three-level optimization problem. Therefore, solution methods are based either on enumerative searches (i.e., for each index f being tested, enumerate all possible scenarios θs), or on active set approaches (Varvarezos et al. 1995), both of which are computationally very intensive.

2.2 Impact on objective function

In industry, the impact of parametric variability on the objective function is often translated into economics (e.g., maximize profit and/or performance, minimize cost, etc.). In this paper, we classify the impact on the objective function into two main categories: effect of endogenous uncertainty (cases in which the user only has access to imperfect information, Sect. 2.2.1) and of exogenous uncertainty with perfect information (Sect. 2.2.2).

2.2.1 Cost of endogenous uncertainty (imperfect information)

The values of uncertain parameters may not be known at the time of decision-making, which is typical of endogenous uncertainty sources. In planning and scheduling this situation occurs, for instance, when calculating plans or schedules using supply and demand orders that are not firm, i.e., whose timing and/or amounts are not known exactly. In Fig. 2, this could correspond to calculating the crude oil blending schedule for the entire week with uncertain pipeline delivery times.

Two measures of the effect of lack of information about parameter values are the Maximum Regret and the Expected Value of Perfect Information (EVPI). They are applicable to situations where there are HAN decisions x 1 in addition to the WAS decisions x 2; i.e., there are at least a few decisions that have to be made before all parameter outcomes are known. Problem (5) below illustrates the two-stage recourse model (Ierapetritou et al. 1996):

Problem (5):

$$ \mathop {Maximize}\limits_{{x_{1} ,x_{2} }} c_{1}^{T} \cdot x_{1} + E_{\theta } \left\{ {c_{2}^{T} (\theta ) \cdot x_{2} } \right\} $$

Subject to

$$ A_{1} \cdot x_{1} \le b_{1} $$
$$ B_{1} \cdot x_{1} + B_{2} (\theta ) \cdot x_{2} - b_{2} (\theta ) \le 0 $$
$$ x_{1} ,x_{2} \ge 0 $$

Here, variables x 1 correspond to the HAN (first-stage) decisions, whereas variables x 2 correspond to the WAS (second-stage) decisions, which depend on the HAN decisions x 1. The WAS model that corresponds to the best possible set of decisions given parameter outcomes θ is:

Problem (6):

$$ F_{1} \left( \theta \right)\mathop { = Maximize}\limits_{{x_{1} ,x_{2} }} \left\{ {c_{1}^{T} \cdot x_{1} + c_{2}^{T} (\theta ) \cdot x_{2} } \right\} $$

Subject to

$$ A_{1} \cdot x_{1} \le b_{1} $$
$$ B_{1} \cdot x_{1} + B_{2} (\theta ) \cdot x_{2} - b_{2} (\theta ) \le 0 $$
$$ x_{1} ,x_{2} \ge 0 $$

The HAN model, which corresponds to the best possible set of WAS decisions x 2 given a set of fixed HAN decisions (x *1 ) and parameter outcomes θ, is:

Problem (7):

$$ F_{2} \left( {x_{1}^{*} ,\theta } \right)\mathop { = Maximize}\limits_{{x_{2} }} \left\{ {c_{1}^{T} \cdot x_{1}^{*} + c_{2}^{T} (\theta ) \cdot x_{2} } \right\} $$

Subject to

$$ B_{1} \cdot x_{1}^{*} + B_{2} (\theta ) \cdot x_{2} - b_{2} (\theta ) \le 0 $$
$$ x_{2} \ge 0 $$

The regret function (R) corresponds to the “missed opportunity” of not having made the best decision possible given the (WAS) parameter outcomes θ. If all HAN decisions became WAS decisions, users would make the best possible decisions, since they would have perfect knowledge of parameter values before deciding. Regret with respect to a HAN decision x *1 and a parameter outcome θ is calculated as follows:

$$ {\text{R}}\left( {x_{1}^{*} ,\theta } \right) \, = F_{ 1} \left( \theta \right) - F_{ 2} \left( {x_{1}^{*} ,\theta } \right) $$

A practical example of the use of Regret functions in planning and scheduling is “back-casting”. At the end of the decision-making horizon, the backcast consists of calculating the decision based on all parameter values that were made available at the end of the decision-making horizon, and then comparing this “perfect” decision to the one that was implemented in the system. In other words, the backcast is a measure of regret for the decisions that have been made.

Given all possible parameter outcomes θ, the Maximum Regret (MaxR) corresponds to the regret based on the worst possible parameter outcomes in the system given a certain set of HAN decisions x *1 . Maximum Regret can thus be expressed as:

$$ {\text{MaxR}}\left( {x_{1}^{*} } \right) \, = {\text{Maximize}}\left( {{\text{over all}}\;\theta } \right)\left\{ {F_{ 1} \left( \theta \right) - F_{ 2} \left( {x_{1}^{*} , \theta } \right) } \right\} \approx {\text{Max}}\left( {{\text{over all}}\theta_{s} } \right) \, \left\{ {F_{ 1} \left( {\theta_{s} } \right) - F_{ 2} \left( {x_{1}^{*} , \theta_{s} } \right)} \right\} $$

(given a set of scenarios from the parameter space)

The expected value of perfect information (EVPI) is a less conservative measure of opportunity loss than Maximum Regret since the former considers parameter probability distribution. Therefore, parameter outcomes that have a small probability of occurring will have a small contribution to the overall EVPI. EVPI can be expressed as:

$$ {\text{EVPI}}\left( {x_{1}^{*} } \right) \, = E_{\theta } \left\{ {F_{ 1} \left( \theta \right) - F_{ 2} \left( {x_{1}^{*} , \theta } \right)} \right\} \approx \sum\limits_{{s{ \in }S}} {p_{s} } \cdot \left[ {F_{ 1} \left( {\theta_{s} } \right) - F_{ 2} \left( {x_{1}^{*} , \theta_{s} } \right)} \right] $$

2.2.2 Cost of exogenous uncertainty with perfect information

In some cases, the user may wish to assess how much the uncertainty that exists in the system will impact decisions, even if those are made after parameter outcomes are known. This is different from EVPI and Maximum Regret since in this case the dynamic, temporal aspect of decision-making (HAN versus WAS) is not considered: all decisions are assumed to be WAS. An additional difference is that in this case it is exogenous sources of uncertainty being considered as opposed to endogenous ones.

In Fig. 2, this assessment would indicate the difference between the optimal schedule for a delivery of crude oils with the “best possible” qualities and the optimal schedule for a delivery with the “worst possible” qualities. This topic has been addressed by Chinneck and Ramadan (2000), Zyngier (2006) and Zyngier and Marlin (2006). In these studies, the objective function difference between the best-case parameter realizations (“best-case scenario”) and worst-case parameter realizations (“worst-case scenario”) is calculated and expressed as an objective function range (OFR). While Chinneck and Ramadan (2000) applied enumerative methods to solve this problem, Zyngier (2006) and Zyngier and Marlin (2006) used a single-stage optimization problem. The nominal optimization problem is illustrated below.

Problem (8):

$$ \mathop {Minimize}\limits_{x,y} \, \left\{ {c\left( \theta \right)^{T} \cdot\, x + w \cdot \left( {\sum\limits_{in} {y_{in}^{ + } } + \sum\limits_{eq} {\left( {y_{eq}^{ + } + y_{eq}^{ - } } \right)} } \right)} \right\} $$

Subject to

$$ g_{in} \left( {y_{in} ,\theta } \right) = A_{in} \left( \theta \right) \cdot x - b_{in} \left( \theta \right) - y_{in}^{ + } \ge 0 $$
$$ g_{eq} \left( {y_{eq} ,\theta } \right) = A_{eq} \left( \theta \right) \cdot x - b_{eq} \left( \theta \right) - y_{eq}^{ + } + y_{eq}^{ - } = 0 $$
$$ y_{in}^{ + } ,y_{eq}^{ + } ,y_{eq}^{ - } ,x \ge 0 $$

The best-case scenario (BC) stated in Problem (9) determines the best possible parameter realization in the system. This problem is very similar to the nominal Problem (8), except that the parameters are assumed to lie within upper and lower bounds. However, Problem (9) is nonlinear due to the bilinear terms A(θ)x in the constraints and c(θ)T x in the objective function.

Problem (9):

$$ {\text{BC}} = \mathop {Minimize}\limits_{x,y,\theta } \left\{ {c\left( \theta \right)^{T} \cdot\, x + w \cdot \left( { \sum _{in} y_{in}^{ + } + \sum _{eq} \left( {y_{eq}^{ + } + y_{eq}^{ - } } \right)} \right)} \right\} $$

Subject to

$$ \theta^{LB} \le \theta \le \theta^{UB} $$
$$ g_{in} \left( {y_{in} ,\theta } \right) = A_{in} \left( \theta \right) \cdot x - b_{in} \left( \theta \right) - y_{in}^{ + } \ge 0 $$
$$ g_{eq} \left( {y_{eq} ,\theta } \right) = A_{eq} \left( \theta \right) \cdot x - b_{eq} \left( \theta \right) - y_{eq}^{ + } + y_{eq}^{ - } = 0 $$
$$ y_{in}^{ + } ,y_{eq}^{ + } ,y_{eq}^{ - } ,x \ge 0 $$

The formulation in Problem (10) is used for determining the worst possible parameter realizations in the system, also known as worst-case scenario (WC). Differently from the feasibility test, the worst-case problem is not based on a fixed solution x * from the original optimization problem.

Problem (10):

$$ {\text{WC}} = \mathop {Maximize}\limits_{\theta } \left\{ {c\left( \theta \right)^{T} \cdot \,x + w \cdot \left( { \sum _{in} y_{in}^{ + } + \sum _{eq} \left( {y_{eq}^{ + } + y_{eq}^{ - } } \right)} \right)} \right\} $$

Subject to

$$ \theta^{LB} \le \theta \le \theta^{UB} $$
$$ \mathop {Minimize}\limits_{x,y} \left\{ {c\left( \theta \right)^{T} \cdot\, x + w \cdot \left( {\sum\limits_{in} {y_{in}^{ + } } + \sum\limits_{eq} {\left( {y_{eq}^{ + } + y_{eq}^{ - } } \right)} } \right)} \right\} $$

Subject to

$$ g_{in} \left( {y_{in} ,\theta } \right) = A_{in} \left( \theta \right) \cdot x - b_{in} \left( \theta \right) - y_{in}^{ + } \ge 0 $$
$$ g_{eq} \left( {y_{eq} ,\theta } \right) = A_{eq} \left( \theta \right) \cdot x - b_{eq} \left( \theta \right) - y_{eq}^{ + } + y_{eq}^{ - } = 0 $$
$$ y_{in}^{ + } ,y_{eq}^{ + } ,y_{eq}^{ - } ,x \ge 0 $$

If the objective function of the original problem only contains penalty variables y (i.e., decision variables x are fixed), the worst-case problem WC is equivalent to the feasibility problem. The objective function range (OFR) is calculated as:

$$ {\text{OFR}} = \left( {{\text{BC}}\,{-}\,{\text{WC}}} \right) $$

An OFR > 0 is not caused by lack of information about parameter realizations, thus differing from the Maximum Regret problem: OFR is a measure of the effect of parameter variability in a system given wait-and-see variables only. In other words, both BC and WC problems assume that (best- and worst-case) parameter realizations are perfectly known when decisions x have to be made. Therefore, OFR is useful for assessing (or vetting) the effect of the variability of exogenous variables (for instance, raw material properties or timing of demand orders) on the system in question.

3 Adjustment: reducing the impact of endogenous uncertainty

Section 2 addressed Assessment methods, in which the effect of uncertainty was evaluated in order to determine its impact on feasibility and on objective function value. Adjustment methods, on the other hand, focus on making decisions that account for endogenous uncertainty. Similar to Assessment methods, Adjustment methods may be based on guaranteeing feasibility of the solution, or on minimizing the impact of uncertainty on the objective function.

Naturally, the immunization of the problem to uncertainty comes at a price: there is usually a compromise between the objective function value of a problem and the robustness of the decision with respect to uncertainty. This can be illustrated through the example in Fig. 2. The blended crude oils must satisfy maximum sulphur specifications. If decision-makers are unsure of the sulphur content of incoming crude oils, they will most likely impose a processing “safety margin” such that blend specifications are met. If product is not within specifications, it may be either discarded or submitted to expensive re-processing operations. On the other hand, imposing a “safety margin” (also known as giveaway) reduces process profit margins.

Decision adjustment based on the impact of uncertainty on feasibility may be calculated by reformulating the original formulation as a Stochastic Programming (SP) problem. SP is defined as an optimization problem in which one or more of the data elements is represented by a random variable (Sen and Higle 1999). There are two different methods in SP that are relevant to this paper: Recourse Programming and the use of Probabilistic constraints. Recourse Programming (Sect. 3.1) incorporates the dynamic aspect of parameter outcomes since there is differentiation between HAN and WAS decisions. On the other hand, Probabilistic constraints (Sect. 3.2) are based on backing off from constraints to ensure that they will be satisfied to a certain probability level. Another adjustment alternative is to accept a certain level of infeasibility in the constraints, as is the case in the Feasibility Tolerance approach (Sect. 3.3).

The adjustment of decisions based on the effect of uncertainty on the objective function, on the other hand, can be addressed by calculating the decision which will be the least sensitive to the parameter outcomes. The two approaches outlined in Sect. 3.4 are the minimization of EVPI and the minimization of the Maximum Regret.

3.1 Impact on feasibility: recourse programming

Recourse Programming considers that not all parameter outcomes are known at the time of decision-making, and therefore variables are separated into HAN and WAS decisions. In the following sub-sections, different types of recourse problems are outlined.

3.1.1 Simple recourse

The simple recourse problem (also known as WAS analysis or scenario optimization) is a special case of Recourse Programming, used in scenario analyses or what-if analyses. In this type of problem, all scenarios are solved simultaneously such that “reasonable” decisions can be made (Sen and Higle 1999; Dembo 1991), which may be infeasible for one or more scenarios.

In simple recourse, infeasibilities in second-stage decisions are penalized in objective function, weighted by the probability of occurrence of each individual scenario. Consider the following optimization problem:

Problem (11):

$$ \mathop {Maximize \, }\limits_{x} \left\{ {c^{T} x} \right\} $$

Subject to

$$ A_{d} \cdot x = b_{d} $$
$$ A_{u} \cdot x = b_{u} $$
$$ x \ge 0 $$

The corresponding single recourse reformulation of Problem (11) is stated as:Problem (12):

$$ \mathop {Maximize}\limits_{x} \left\{ {c^{T} x - \sum\limits_{u} {w_{u} } \sum\limits_{s} {p_{s} \cdot \left( {y_{u,s}^{ + } + y_{u,s}^{ - } } \right)} } \right\} $$

Subject to

$$ A_{d} \cdot x = b_{d} $$
$$ A_{u,s} \cdot x = b_{u,s} + y_{u,s}^{ + } - y_{u,s}^{ - } $$
$$ x,y_{u,s}^{ + } ,y_{u,s}^{ - } \ge 0 $$

where w u is the penalty weight for violating constraint u and p s is the probability of occurrence of scenario s. Whenever constraints associated with second-stage decisions are not satisfied, there are associated non-zero penalty variables (y u,s ).

Scenario optimization can be implemented in a very simple fashion to obtain “reasonable” decisions x by solving (s + 1) optimization problems of the same size of the original Problem (11) (Dembo 1991). However, as previously noted, this formulation allows for infeasible solutions for some of the scenarios, which may not be an appropriate alternative for applications where feasibility is required.

3.1.2 General (or random) recourse

In two-stage or random recourse problems, the first-stage variables must allow for feasible second-stage WAS decisions. In this case, no penalty terms are included for infeasibility of constraints that involve WAS decisions x 2. As a result of solving general recourse problems, the user obtains a set of s feasible solutions for each of the second-stage variables that depend on (future) parameter realizations (x 2s ). In general, only the first-stage decision variables x 1 are reported and implemented after solving a general recourse problem. A general recourse problem can be seen below:

Problem (13):

$$ \mathop {Maximize}\limits_{{x_{1} ,x_{2s} }} \, c_{1}^{T} \cdot x_{1} + \sum\limits_{s} {p_{s} \cdot c_{2}^{T} (\theta_{s} ) \cdot x_{2s} } $$

Subject to

$$ A_{d} \cdot x_{1} \le b_{d} $$
$$ A_{1s} \cdot x_{1} + A_{2} (\theta_{s} ) \cdot x_{2s} - b(\theta_{s} ) \le 0 $$
$$ x_{1} ,x_{2s} \ge 0 $$

When the second-stage matrix [A 1 A 2] is the same for all scenarios, the problem is said to have Fixed Recourse. It is interesting to note that simple recourse problems are a special type of general recourse problems with fixed recourse in which the second set of inequality constraints are equality constraints, the fixed second-stage matrix is equal to [I–I] and b is a vector of zeros. These problems can also be interpreted as a general recourse problem with no WAS decisions.

If all second-stage problems are feasible for any choice of first-stage variables, i.e., if the first-stage variables are unconstrained, the problem is said to have Complete Recourse. If all second-stage problems are feasible given any of the first-stage variables that satisfy the first-stage constraints, the problem is said to have Relatively Complete Recourse (Sen and Higle 1999).

3.2 Impact on feasibility: probabilistic constraints

In the case where all decisions must be made before parameter values are known (i.e., all variables are HAN decisions), one of two solution strategies is usually adopted: (1) to increase the likelihood of making feasible decisions, or (2) to require the solution to lie within pre-established constraint violation bounds. Such strategies are also referred to as “Robust Optimization” problems in the literature. The former is based on probabilistic constraints, which results in distancing (“backing off”) from system bounds, whereas the latter corresponds to the feasibility tolerance approach, which allows small constraint violations (see Sect. 3.3).

Probabilistic (or chance) constraints (Charnes and Cooper 1963) restrict the probability of constraint violation to a user-specified level. In other words, the use of probabilistic constraints determines the decision x * which will satisfy the constraints at least a certain percentage of the time (e.g., 95 %) by incorporating information about the uncertain parameter distribution. An optimization problem with chance constraints can be seen below:

Problem (14):

$$ \mathop {Maximize}\limits_{x} \left\{ {c^{T} x} \right\} $$

Subject to

$$ P\left( {A \cdot x - b \ge 0} \right) \ge p $$
$$ x \ge 0 $$

When the probability distributions across constraints are independent from each other (i.e., when they are not correlated), Problem (14) can be reformulated as: Problem (15):

$$ \mathop {Maximize}\limits_{x} \left\{ {c^{T} x} \right\} $$

Subject to

$$ P\left( {a_{i} \cdot x - b_{i} \ge 0} \right) \ge p $$
$$ x \ge 0 $$

From Ben-Tal and Nemirovski (1998), Problem (15) can be reformulated into the equivalent second-order conic programming problem: Problem (16):

$$ \mathop {Maximize}\limits_{x} \left\{ {c^{T} x} \right\} $$

Subject to

$$ a_{i,nom} \cdot x - b_{i,nom} - c\left\| {V_{i}^{1/2} \left( {\begin{array}{*{20}c} x \\ { - 1} \\ \end{array} } \right)} \right\|_{2} \ge 0 $$
$$ x \ge 0 $$

In Problem (16), the subscript nom refers to the nominal parameter values. Additionally, \( c = z_{p/ 2} = \varPhi^{ - 1} \left( { 1 - p/ 2} \right) \), where Φ(.) is the univariate normal distribution function with zero mean and unit variance. For a constraint that must be satisfied 95 % of the time, z p/2 = 1.96. Assuming uncorrelated parameters in each constraint i,

$$ V_{i} = \left[ {\begin{array}{*{20}c} {\sigma_{{a_{i,1} }}^{2} } & {} & {} & {} \\ {} & {\sigma_{{a_{i,2} }}^{2} } & {} & {} \\ {} & {} & \cdots & {} \\ {} & {} & {} & {\sigma_{{b_{i} }}^{2} } \\ \end{array} } \right], $$

where σ 2(.)  = variance of (.)

3.3 Impact on feasibility: feasibility tolerance

In some instances of Robust Optimization, the user may want to assign a feasibility tolerance to the optimization constraints, i.e., constraints are allowed to be “slightly” infeasible. This is the basic principle of the Reliability (or Feasibility Tolerance) Approach first outlined in Ben-Tal and Nemirovski (2000). These authors developed a method to obtain adjusted solutions to linear programming problems. This approach was later extended to mixed-integer linear programming (MILP) problems by Lin et al. (2004). In the problems below, only the formulation for LP problems is shown. Consider the following LP:

Problem (17):

$$ \mathop {Maximize \, }\limits_{x} c^{T} \cdot x $$

Subject to

$$ A \cdot x \le b $$
$$ x^{LB} \le x \le x^{UB} $$

Here, uncertainty is assumed to be in any inequality constraint coefficient (a i,n and/or b i ). For the case of bounded uncertainty, the uncertain parameters lie within the following intervals:

$$ \left| {a_{i,n} - a_{i,n,nom} } \right| \le \varepsilon \cdot \left| {a_{i,n,nom} } \right|\,{\text{and \,therefore }}\left| {a_{i,n} } \right| \le \left| {a_{i,n,nom} } \right| + \varepsilon \cdot \left| {a_{i,n,nom} } \right| $$
$$ \left| {b_{i} - b_{i,nom} } \right| \le \varepsilon \cdot \left| {b_{i,nom} } \right|\,{\text{and \,therefore }}\left| {b_{i} } \right| \le \left| {b_{i,nom} } \right| + \varepsilon \cdot \left| {b_{i,nom} } \right| $$

where ε > 0 is a user-defined “uncertainty level”. Taking the largest deviation of parameter realizations from the nominal values and substituting them into the original problem, the (ε, δ)-interval robust counterpart of the original problem is obtained. In this robust problem, δ is called an “infeasibility tolerance”:

Problem (18):

$$ \mathop {Maximize}\limits_{x,u} \, c^{T} \cdot x $$

Subject to

$$ A \cdot x \le b $$
$$ \sum\limits_{n} {a_{i,n,nom} } \cdot x_{n} + \varepsilon \cdot \sum\limits_{n} {\left| {a_{i,n,nom} } \right|} \cdot u_{n} \le b_{i} - \varepsilon \cdot \left| {b_{i,nom} } \right| + \delta \cdot \hbox{max} \left( {1,\left| {b_{i,nom} } \right|} \right) $$
$$ - u_{n} \le x_{n} \le u_{n} $$
$$ x^{LB} \le x \le x^{UB} $$

Note that the robust counterpart of an LP problem (Problem (18)) is still a linear problem. Similarly, the robust counterpart of a MILP problem is also a MILP. In addition to bounded uncertainty region descriptions, ellipsoidal descriptions may also be used by replacing the bounded uncertainty constraints with the ones below:

$$ a_{i,n} = \left( {1 + \varepsilon \cdot \xi_{i,n} } \right) \cdot a_{i,n,nom} $$
$$ b_{i} = \left( {1 + \varepsilon \cdot \xi_{i} } \right) \cdot b_{i,nom} $$

In these equations, ξ i,n and ξ i are random variables distributed symmetrically in the interval [−1,1]. Given that the probability of violation of the i-th constraint is at most κ (also known as the constraint’s “reliability level”), the (ε, δ, κ)-robust counterpart can be described as:

Problem (19):

$$ \mathop {Maximize}\limits_{x,u,z} \, c^{T} \cdot x $$

Subject to

$$ A \cdot x \le b $$
$$ \sum\limits_{n} {a_{i,n,nom} } \cdot x_{n} + \varepsilon \cdot \left[ {\sum\limits_{n} {\left| {a_{i,n,nom} } \right|} \cdot u_{n} + \varOmega \cdot \sqrt {\sum\limits_{n} {a_{i,n,nom}^{2} \cdot z_{i,n}^{2} } + b_{i,nom}^{2} } } \right] \le b_{i} + \delta \cdot \hbox{max} \left( {1,\left| {b_{i,nom} } \right|} \right) $$
$$ - u_{n} \le x_{n} - z_{i,n} \le u_{n} $$
$$ x^{LB} \le x \le x^{UB} $$

where Ω is a positive parameter with κ = exp{−Ω2/2}. For example, for a 5 % reliability level, Ω would be roughly equal to 2.45. The general symmetric description of uncertainty in Problem (19) is less conservative than adopting simple bounds for the uncertain parameters. However, the user is faced with an increased computational burden since the original LP problem now becomes a nonlinear problem.

3.4 Impact on objective function: minimax regret/min EVPI

In Sects. 3.1, 3.2 and 3.3, decision adjustments were based on feasibility criteria. Another possible criterion for adjusting decisions is the impact of uncertainty on objective function value. Similar to the uncertainty assessment methods described in Sect. 2.2, the adjustment methods based on the objective function value assist in making decisions that minimize the impact of parameter uncertainty on the objective function.

These approaches may also be based on worst-case parameter realizations (Maximum Regret approach) or on expected parameter realizations (EVPI approach). The Minimax Regret (MinMaxR) problem finds decisions x 1 that minimize the Maximum Regret (Averbakh 2000), and can be described as follows.

Problem (20):

$$ MinMaxR = \mathop {Minimize}\limits_{x} \left[ {MaxR\left( x \right)} \right] $$

Subject to

$$ MaxR\left( x \right) \, = \mathop {Maximize}\limits_{\theta } \left[ {F_{ 1} \left( \theta \right) - F_{ 2} \left( {x, \theta } \right)} \right] $$

Subject to

$$ \theta^{LB} \le \theta \le \theta^{UB} $$

As a bilevel problem, Problem (20) can be solved by replacing the MaxR(x) subproblem with its optimality conditions. However, this results in a nonlinear programming problem (or a MINLP), since complementarity constraints arise from the bounds on parameter values. Instead of parameter bounds, Problem (20) may be reformulated using scenarios in the MaxR(x) subproblem, resulting in the following problem:

Problem (21):

$$ MinMaxR = \mathop {Minimize}\limits_{x} \left[ {MaxR\left( x \right)} \right] $$

Subject to

$$ MaxR\left( x \right) = \mathop {Maximize}\limits_{{\theta_{s} }} \left[ {F_{1} (\theta_{s} ) - F_{2} (x,\theta_{s} )} \right] $$

The following methodology can be used to solve scenario-based formulations of the minimization of Max Regret in Problem (21) or EVPI:

  1. (1)

    Solve F 1(θ s ) for every scenario s ∈ S, and obtain a set of x * s .

  2. (2)

    For each scenario s ∈ S, solve F 2(x * s , θ s′) for every s′ ∈ S, where s′ ≠ s (since regret is zero when s′ = s).

  3. (3)

    Find MaxR(x * s ) = Max (over all θ s′ ) F 2(x * s , θ s′) for all x * s . Alternatively, we can calculate the \( {\text{EVPI}}\left( {{\text{for each}}\;x_{s}^{*} } \right) = \sum _{{s{\prime \in }S}} p_{{s{\prime }}} \cdot \left[ {F_{ 1} \left( {\theta_{s} } \right) - F_{ 2} \left( {x_{s}^{*} , \theta_{{s{\prime }}} } \right)} \right] \), where s′ ≠ s.

  4. (4)

    Find x * s which yields the smallest MaxR(x * s ). Alternatively, we could find x * s which yields the smallest EVPI.

  5. (5)

    The solution x * s from step 4 is the HAN decision that minimizes the MaxR (or EVPI) given scenarios s ∈ S.

The above methodology requires the solution of \( \left( {s + s{ \cdot }\left( {s - 1} \right) } \right) = {\mathbf{s}}^{{\mathbf{2}}} \) optimization problems which have the same structural characteristics (LP, MILP, etc.) as the original problem.

4 Abatement: reducing the cost of exogenous uncertainty

As previously mentioned, there is value in assessing the impact of uncertainty and in adjusting decisions based on its existence. In some cases, it is possible to significantly reduce exogenous uncertainty in model parameters.

In some processes, parameters may be physically measurable (such as octane in gasoline) and extra instrumentation can be installed in order to obtain accurate information about their true values. Instrumentation equipment, installation and maintenance, however, can be very expensive. Furthermore, model parameters may not be physically measurable in some systems.

An alternative to physically measuring model parameters is to develop a more accurate first-principles model. In planning and scheduling applications, for instance, more accurate forecasting models could be used in order to better determine the future supply and demand profiles in the system, An excellent reference to forecasting models is the book by Box et al. (1994). However, when detailed first-principles models are not readily available, they may be very expensive to develop and even then might not yield the required accuracy.

A useful “model enhancement” technique widely used in Process Control is the incorporation of feedback to the system in order to continuously improve model representation (Kelly and Zyngier 2008a). In this case, the feedback parameter obtained by comparing measured variables to their model predictions accounts for some model inaccuracies, given that this value is incorporated in the following decision cycle.

Finally, model parameters can be re-estimated based on available process measurements. Since typical data variation in the system may be limited, significant improvement in estimated parameter accuracy is usually obtained from designing plant experiments. Traditional factorial design of experiments usually requires significant process perturbations which disturb plant operations. In order to overcome this issue, techniques for optimal design of experiments have been developed that reduce the number of plant experiments while still enabling the reduction of parameter uncertainty to desired levels (Draper and Smith 1998; Zyngier and Marlin 2006). Since this paper focuses on the categorization of optimization problems with uncertain parameters, a more in-depth analysis of design of experiments and forecasting methods is suggested as further exercise to the reader.

5 Solution simplification approaches

The solution of many of the optimization problems presented in this paper may prove to be computationally challenging, given that they sometimes result in large-scale nonlinear programs or mixed-integer nonlinear programs. Therefore, strategies have been devised to enable the solution of industrial-sized problems in reasonable time. Two main types of solution simplification strategies are commonly adopted: one which maintains a continuous description of the parameter space, and another, in which (discrete) samples of the parameter space are used. Sometimes a combination of simplification methods may be possible.

5.1 Continuous approaches

A very common approach to improve the management of computational complexity is to simplify the original deterministic model by limiting its spatial scope. Instead of considering an entire plant in a single large model, the original model may instead be broken down into smaller sub-models, which are then solved separately. While this technique does indeed reduce the computational effort involved in the solution of each sub-problem, it adds the complexity of coordinating the different sub-models. A detailed discussion on several aspects of decentralized systems in industry, as well as a strategy for obtaining a globally feasible solution across all sub-models, can be found in Kelly and Zyngier (2008b).

Another simplification strategy is to limit the complexity of correlations between variables in the system. In Fig. 2, for instance, fixed blend recipes could be used to avoid nonlinear crude oil blending equations. Nonlinear relationships such as blending correlations may also sometimes be replaced by linear counterparts (e.g., by using blending indices). Some common simplification strategies are separable programming and piecewise linear representations of nonlinear functions (Williams 2013). These techniques simplify the solution of the problems at the cost of a less accurate representation of the system. This issue may be more of less relevant depending on the nonlinear characteristics of the process, the operating region, and the specific use of the model (e.g., long-term planning models versus process simulation models).

Finally, the robust optimization methods described in Sect. 3.2 often rely on ellipsoidal parameter uncertainty regions, which are reformulated into quadratic constraints. Ben-Tal and Nemirovski (2001) proposed a polyhedral approximation of the ellipsoidal parameter region which maintains the problem’s original structural characteristics at the cost of an increased number of linear constraints. The number of additional linear constraints depends on the number of approximation points on the ellipse. Several additional approximation methods for linear and mixed-integer linear programs under uncertainty were also presented by Li et al. (2011).

5.2 Discrete approaches

Another approach for limiting complexity when solving optimization problems under uncertainty is to sample the parameter uncertainty region and solve several deterministic optimization problems, one for each sample. These parameter samples are also known as scenarios (or “cases”).

For single-stage decision-making problems, such as simple recourse or scenario optimization (Dembo 1991), there is a root-scenario (corresponding to the original deterministic problem) and several leaf-scenarios, each corresponding to a modification to the root-scenario. In this case, any one of the (root or leaf) scenarios can be solved independently, i.e., no knowledge about the adjacent scenarios is required. In Scenario optimization, all (root and leaf) scenarios are solved at once in a single optimization problem. Dembo (1991) describes how this “aggregated” optimization problem can be broken up into smaller optimization problems which would have to be solved once for each scenario, plus one time to combine all previous solutions.

For multi-stage decision-making problems such as two- or multi-stage recourse problems not every parameter realization is known at the root-node. The subsequent leaf-nodes represent the different parameter outcomes. In this case, a branch-scenario comprises the combination of the root-node with as many leaf-nodes as there are stages in the decision tree.

Solving deterministic optimization problems is much simpler than its uncertain counterpart. In addition, the overall parameter distribution is fairly well-represented given a certain number of samples. However, the number of scenarios may be intractable, especially as the number uncertain parameters increases. Taking again the example in Fig. 2, uncertainty could easily be present in the specific gravity and sulphur specifications for five different types of crudes (10 uncertain parameters). If only two values for each uncertain parameter were considered, there would be a total of 210 = 1024 possible parameter value combinations, each corresponding to a different scenario. If three different values for each parameter were considered, the total number of scenarios would increase to 59,049! Adding to this issue, scheduling problems are dynamic in nature, so additional scenarios may be necessary for temporal uncertainties, such as the time of raw material delivery, processing times, etc.

In order to reduce the number of scenarios, it is common industrial practice for domain experts to create a set of scenarios to be analyzed. This reduced set is then considered to be a representative sampling of the parameter distribution. In other situations, scenarios can be automatically generated with very little or no user input. An automatic scenario generation approach is Monte Carlo sampling, in which parameters are randomly selected from a distribution.

In the context of planning and scheduling, another alternative to the somewhat blind sampling techniques such as Monte Carlo is to automatically generate outcome-orders. In this case, a set of parameter outcome instances (scenarios) can be automatically generated given, for example, a certain set of exogenous market-orders in the root scenario: if market-orders only exist for product A, there is no need to generate scenarios for different parameter outcomes related to product B. This concept is an extension of obtained-orders (Kelly and Zyngier 2012).

When working on a multi-scenario framework, a systematic tool can be quite useful for comparing different scenarios. The comparison may simply be for the purposes of analysis by the user, or it may be used in order to simplify the solution of certain types of problems.

Scenario comparison is particularly useful in multi-stage recourse programming approaches, which are computationally very demanding. Rockafellar and Wets (1991) developed a method to search for (and subsequently fix) commonalities across different scenarios in order to ease the computational burden of a multi-stage recourse programming problem. This concept is related to the proximate optimality principle (POP) (Glover and Laguna 1997), which is applied to MILP problems.

If several scenarios are created for a system, there is the need for storing those scenarios in a database. Whenever there is an actual parameter outcome in the system (e.g., at every planning or scheduling cycle), this scenario can be included in the database, and the probability of occurrence of that particular scenario can be automatically updated. In fact, a heuristic can be created based on a forgetting factor that can be used to update the probability of occurrence of “unlikely” scenarios: if the probability of a scenario is below a certain value, this scenario may be eliminated from the database.

6 Conclusions

This paper focused on reducing the well-known gap between state-of-the-art technology in academia and industrial best practices in the vast field of optimization under uncertainty. Most reviews in the literature have approached the topic by mapping existing optimization methods to applications. In this sense, the categorization presented here is of great value to industrial practitioners, since it is more natural and convenient when determining what kind of optimization methods and techniques to use bearing in mind the type of decision being made. In addition to contributing with a novel categorization, this paper included recent advances for different types of decision-making problems. Finally, solution simplification techniques including issues related to scenario generation and management were presented.