A Unified Framework for Adjustable Robust Optimization with Endogenous Uncertainty

Robust optimization is an approach to decision making under uncertainty that has gained tremendous popularity in the optimization community over the last two decades. It is particularly attractive in situations in which (i) the set of possible uncertainty realizations, commonly referred to as the uncertainty set, is known but the probability distribution is not, (ii) feasibility over the entire uncertainty set or the worst-case performance is of main interest, or (iii) alternative approaches, such as scenario-based stochastic programming, are computationally significantly less tractable. Earlier works on robust optimization ¹, ² were limited to the static case, which only considers here-and-now decisions that need to be determined before the uncertainty is realized. In contrast, adjustable robust optimization (ARO) ³ provides a framework that also incorporates wait-and-see (or recourse) decisions, which can be determined after the true values of some uncertain parameters are revealed. This makes ARO suitable for a large set of sequential decision-making problems, hence greatly expanding the applicability of the robust optimization paradigm. There has been a plethora of theoretical and practical contributions addressing a variety of ARO problems. A particular research focus has been the development of tractable approximations, e.g. in the form of decision rules ³, ⁴, and solution methods ⁵, ⁶, with many of the more recent efforts directed at the efficient handling of discrete recourse decisions ⁷, ⁸, ⁹, ¹⁰, ¹¹, ¹². We refer the reader to Yanıkoğlu et al. ¹³ for a comprehensive survey on ARO.

The term “adjustable robust optimization” had not appeared in the process systems engineering (PSE) literature until 2016 ¹⁴, ¹⁵, ¹⁶. Only then, as formally discussed by Zhang et al. ¹⁷, the PSE community realized that it actually has been applying the concept of (two-stage) ARO for decades, but under a different name: flexibility analysis ¹⁸. Many of the approaches developed in this line of work resemble the ones presented in the robust optimization literature. However, traditional flexibility analysis focuses primarily on nonlinear problems, which may be the reason why it so far has not been recognized or noticed by the operations research community. In the last few years, the number of ARO-related works in PSE has increased rapidly, addressing diverse applications in process design ¹⁹, ²⁰, planning and scheduling ¹⁴, ¹⁵, ¹⁶, ²¹, ²², ²³, ²⁴, model predictive control ²⁵, ²⁶, ²⁷, supply chain optimization ²⁸, ²⁹, etc.

In stochastic optimization, one distinguishes between exogenous and endogenous uncertainty. While exogenous uncertainty is not affected by the decision maker’s actions, certain properties of endogenous uncertain parameters are decision-dependent. Endogenous uncertainty has its origin in stochastic programming ³⁰, and mainly two types of endogenous uncertainty have been considered in the literature: type 1 where decisions alter the underlying probability distribution of an uncertain parameter ³¹, ³², ³³, and type 2 where decisions affect the time at which an uncertain parameter materializes or its true value is revealed. The vast majority of existing works address type-2 endogenous uncertainty ³⁴, ³⁵, ³⁶, ³⁷, ³⁸, ³⁹, ⁴⁰, ⁴¹, ⁴², ⁴³. Here, the main challenge is the modeling of decision-dependent nonanticipativity, which is typically achieved by encoding a conditional scenario tree. The size of this scenario tree grows exponentially with the number of uncertain parameters and decisions affecting the uncertainty, which leads to dramatically increased computational complexity compared to the case with only exogenous uncertainty. Hence, most research efforts have focused on the development of more efficient formulations ³⁵, ³⁶, ³⁸, ⁴², ⁴³ and solution methods ³⁵, ³⁹, ⁴⁰, ³⁷, ⁴¹, ⁴³. We refer to Apap and Grossmann ⁴³ for a comprehensive review of stochastic programming with endogenous uncertainty.

Only recently, endogenous uncertainty has also been considered in robust optimization. Poss ⁴⁴ and Nohadani and Sharma ⁴⁵ address static robust optimization with decision-dependent polyhedral uncertainty sets. A similar approach is taken by Lappas and Gounaris ⁴⁶, who further extend their framework to consider multistage robust process scheduling where the materialization of task-specific uncertainties, such as processing time and production yield, depends on the execution of the task ¹⁴, ²²; however, the uncertainty set is only affected by first-stage decisions, and all recourse variables are continuous. Avraamidou and Pistikopoulos ⁴⁷ apply multiparametric programming to address endogenous uncertainty in two-stage robust optimization. Finally, Feng et al. ⁴⁸ consider the multistage case with both continuous and binary recourse as well as uncertainty sets that can be affected by decisions at every stage, for which a decision rule approach is applied to derive tractable approximations.

The above-mentioned references investigate problems in which decisions directly affect the stochastic nature of uncertain parameters, which in the robust optimization context translates into uncertainty sets whose shape, size, or dimensionality may be decision-dependent. Also, although the materialization of uncertain parameters can be decision-dependent, it is assumed that the true values of uncertain parameters are observed immediately after their materialization. In a series of recent works, Vayanos and coworkers ⁴⁹, ⁵⁰, ⁵¹ consider robust optimization with decision-dependent information discovery ³⁸, where decisions determine whether and when uncertain parameters are observed. This constitutes a conceptually different type of endogenous uncertainty, where, instead of an underlying stochastic process, the source of uncertainty is the lack of information, which can be acquired with additional effort. In this case, the uncertainty set is reduced (“shrinks”) with additional observations. The proposed framework provides a means of modeling active learning, which refers to selecting experiments sequentially based on the outcomes of previous experiments. It is hence a promising approach to optimizing the trade-off between exploration and exploitation in sequential decision-making problems, particularly those involving complex constraints. Existing works have applied this approach to the learning of customer behavior through dynamic pricing ⁴⁹ and active preference elicitation with application to housing allocation ⁵¹.

We have come to realize that many problems in PSE require the simultaneous consideration of multiple types of endogenous uncertainty. Examples include strategic capacity planning, design of sensor networks, integrated online process optimization and parameter estimation, and maintenance planning with inspections. To address these problems, we need an approach that can consider all previously described types of endogenous uncertainty simultaneously, which, to the best of our knowledge, does not yet exist in the literature. In this work, we develop such a unified ARO framework, which significantly expands our capability to model data-driven optimization problems under uncertainty, particularly those involving active learning. The main contributions of this work are as follows:

• •

  We introduce a new refined classification of endogenous uncertainty that more comprehensively reflects the current understanding of the subject. We further provide a unifying robust optimization perspective and highlight the connection between endogenous uncertainty and active learning.

• •

  We present two-stage and multistage robust optimization formulations and show that they can be used to simultaneously consider all defined types of endogenous uncertainty subject to polyhedral uncertainty sets.

• •

  A decision rule approach based on previous work ⁴⁸ is employed to develop tractable approximations of the given problems, which involve both continuous and binary recourse variables. One major novelty of this work is the use of auxiliary uncertain parameters to model decision-dependent nonanticipativity in the multistage setting. We derive a reformulation that can be directly solved using off-the-shelf optimization solvers.

• •

  The versatility and efficacy of the proposed modeling framework are demonstrated in several computational case studies, which include plant redesign, maintenance planning with inspections, optimizing revision points in capacity planning, and production scheduling with active parameter estimation.

The remainder of this paper is organized as follows. In Section 2, we propose a new refined classification of endogenous uncertainty and systematically analyze the different types of endogenous uncertainty from a robust optimization perspective. In Section 3, the connection between endogenous uncertainty and active learning is established. We develop the two-stage formulation incorporating all types of endogenous uncertainty in Section 4 before presenting the multistage formulation in Section 5. The proposed decision rule approach is detailed in Section 6. In Section 7, results from the computational studies are presented. Finally, in Section 8, we close with some concluding remarks.

As mentioned in Section 1, the literature distinguishes between type-1 and type-2 endogenous uncertainty. Here, we further refine the type-2 classification and propose the following definition of three different types of endogenous uncertainty:

• •

  Type 1: Decisions alter the probability distribution of uncertain parameters.

• •

  Type 2a: Decisions determine whether and when uncertain parameters materialize, i.e. actually become physically meaningful.

• •

  Type 2b: Decisions determine whether and when the true values of uncertain parameters are observed.

Endogenous uncertain parameters can be of more than one type. For example, a company may alter the probability distribution of the demand for its product by changing the selling price, in which case the product demand is a type-1 endogenous uncertain parameter. In addition, if we still have to decide whether or not to launch the product in the first place, the product demand is also type-2a endogenous since it will only materialize if the product is actually available on the market. Moreover, a customer’s product demand is observed when the order is placed; it is type-2b endogenous if we can affect the time of the order, e.g. by specifying it in a contract.

In robust optimization, instead of specifying a probability distribution, uncertainty is described using an uncertainty set, which is the set of all realizations of the uncertain parameters considered possible in the problem. In other words, robust optimization only requires the support of the probability distribution. A two-stage robust optimization problem can be generally formulated as follows:

where $\bm{x}\in\mathcal{X}$ are the first-stage variables and $\bm{\tilde{x}}\in\widetilde{\mathcal{X}}$ are the second-stage variables, which are functions of the uncertain parameters $\bm{\xi}\in\mathbb{R}^{K}$. The objective and constraint functions are denoted by $f$ and $\bm{g}$, respectively. Problem (1) minimizes the worst-case cost while ensuring that the constraints are satisfied for all $\bm{\xi}\in\Xi$. By applying an epigraph reformulation, a problem of form (1) can be reformulated into a problem of the following form:

where the objective function is deterministic. Formulation (2) will be used in the remainder of this paper as it is more convenient for our discussion and subsequent reformulations.

• Remark

  There is a common misconception that a robust optimization problem has to consider a worst-case cost function. As it is apparent from (2), in theory, one can also consider any deterministic or deterministic equivalent (e.g. expressed in terms of scenarios) cost function. Constraint satisfaction with respect to the entire uncertainty set can be considered independently from the choice of objective function. Often, a non-worst-case objective function is more appropriate (see Section 7 for two examples).

In the case of endogenous uncertainty in the two-stage setting, the uncertainty depends on the first-stage decisions $\bm{x}$. For each type of endogenous uncertainty, we show how $\bm{x}$ affect the following three major components of problem (2):

• •

  the uncertainty set $\Xi$, which is constant in the case of only exogenous uncertainty but depends on $\bm{x}$ if the uncertainty is endogenous, i.e. $\Xi=\Xi(\bm{x})$;

• •

  the deterministic feasible set (DFS) defined as

  $$\mathcal{F}(\bm{x},\bm{\xi}):=\left\{\bm{\tilde{x}}\in\widetilde{\mathcal{X}}:\bm{g}(\bm{x},\bm{\tilde{x}},\bm{\xi})\leq\bm{0}\right\},$$

  which is the set of feasible second-stage solutions given $\bm{x}$ and $\bm{\xi}$;

• •

  and the second-stage recourse decisions $\bm{\tilde{x}}(\bm{\xi})$ as functions of $\bm{\xi}$.

In the context of statistical learning, active learning is the concept of actively gathering information for the purpose of statistical inference. It is also referred to as optimal experimental design as the decisions regarding information discovery are made with an objective in mind, such as minimizing the number of data points required to achieve a given level of confidence in the resulting statistical model. In this section, we highlight the connection between active learning and endogenous uncertainty, and show how it can be conceptualized in a set-based robust optimization framework.

The goal of learning is to gain insights into unknown properties, which can be viewed as uncertain parameters whose level of uncertainty we wish to reduce. Hence, learning is a means of uncertainty reduction. It does so by making new observations that condition the probability distribution; it does not alter the underlying distribution, which is an important distinction. With this perspective, we can model active learning using the notion of endogenous uncertainty. Let $\bm{\xi}\in\mathbb{R}^{K}$ be the uncertain parameters of interest and $\bm{\zeta}\in\mathbb{R}^{M}$ be uncertain parameters that can be observed before the realization of $\bm{\xi}$. Before observing any $\bm{\zeta}$, the probability distribution of $\bm{\xi}$ is $\mathbb{P}(\bm{\xi})$. The decision maker can now choose which $\bm{\zeta}$ to observe in order to improve the current information state with regard to $\bm{\xi}$, indicated by the binary variables $\bm{z}\in\{0,1\}^{M}$ where $z_{i}$ equals 1 if $\zeta_{i}$ is observed and 0 otherwise. After observing the chosen parameters, the updated probability distribution becomes $\mathbb{P}(\bm{\xi}\mid\zeta_{i}=\hat{\zeta}_{i}\;\forall\,i\text{ for which }z_{i}=1)$, where $\bm{\hat{\zeta}}$ denotes a specific observed realization of $\bm{\zeta}$. In a Bayesian sense, $\mathbb{P}(\bm{\xi})$ and $\mathbb{P}(\bm{\xi}|\bm{\zeta})$ can be interpreted as the prior and posterior distributions, respectively. Clearly, in this setting, $\bm{\zeta}$ are type-2b endogenous uncertain parameters. They may also be type-2a endogenous if their materialization is also decision-dependent. Note that $\bm{\xi}$ are considered exogenous uncertain parameters if their materialization and observation are not decision-dependent and if $\mathbb{P}(\bm{\xi})$ and $\mathbb{P}(\bm{\xi}|\bm{\zeta})$ are fixed.

In a robust optimization setting, uncertainty reduction implies reducing the uncertainty set. Using the same notation as above, uncertainty reduction through active learning can then be characterized as follows: Let $\Omega$ be the uncertainty set for the uncertain parameters $(\bm{\xi},\bm{\zeta})$ before the observation of any $\bm{\zeta}$, i.e. $(\bm{\xi},\bm{\zeta})\in\Omega$. Once some $\bm{\zeta}$ are observed (indicated by the binary variables $\bm{z}$) with the realization $\bm{\hat{\zeta}}$, the uncertainty set reduces to $\bar{\Omega}(\bm{z},\bm{\hat{\zeta}})=\{(\bm{\xi},\bm{\zeta}):(\bm{\xi},\bm{\zeta})\in\Xi,\;\bm{\zeta}=\bm{z}\circ\bm{\hat{\zeta}}\}$. Note that $\bar{\Omega}(\bm{z},\bm{\hat{\zeta}})\subseteq\Omega$ for every possible $\bm{\hat{\zeta}}$ as specified by $\Omega$.

In Example 1, we use the term marginal uncertainty set and define it as the projection of the full-dimensional uncertainty set onto the space of a subset of variables, in this case $q$. Generally, given uncertain parameters $\bm{\xi}$ and $\bm{\zeta}$, observing $\bm{\zeta}$ further restricts the marginal uncertainty set for $\bm{\xi}$, denoted by $\Xi$, only if the uncertain parameters are correlated. The geometric interpretation is depicted in Figure 3, where an observation $\bm{\hat{\zeta}}$ results in cutting planes (indicated by the red dashed lines) added to $\Xi$ such that the updated marginal uncertainty set for $\bm{\xi}$ becomes $\overline{\Xi}(\bm{\hat{\zeta}})$.

Modeling active learning as a robust optimization problem with endogenous uncertainty provides an opportunity for integrated optimization and learning, which are two tasks typically performed separately. Central to this problem is the trade-off between exploration and exploitation since our actions affect both the amount of new information and the reward that we receive. The proposed framework can readily incorporate this trade-off and is particularly well suited for problems with complex constraints and recourse decisions, which often cause difficulties for many alternative methods, such as Bayesian optimization ⁵², reinforcement learning ⁵³, and multi-armed bandit optimization ⁵⁴.

In the following, we show how type-1, type-2a, and type-2b endogenous uncertainty can be incorporated in a two-stage robust optimization formulation, eventually leading to a unified model that can capture all these types of endogenous uncertainty simultaneously.

In multistage robust optimization with endogenous uncertainty, decisions that affect the uncertainty can also be recourse variables. Moreover, while the two-stage problem can only consider decisions determining if uncertain parameters materialize or are observed, multistage formulations can incorporate decisions affecting when, i.e. in which stage, uncertain parameters materialize or are observed.

Let $\mathcal{T}=\{1,\dots,T\}$ denote the set of stages and $\mathcal{I}$ the set of uncertain parameters. An uncertain parameter $i\in\mathcal{I}$ can materialize anytime between (and including) given stages $\tau_{i}$ and $\bar{\tau}_{i}$. We define a vector of uncertain parameters $\bm{\xi}_{t}\in\mathbb{R}^{K_{t}}$ that contains all uncertain parameters $i$ for which $\tau_{i}=t$. We further define all uncertain parameters that can materialize in or prior to stage $t$ as $\bm{\xi}_{[t]}=(\bm{\xi}_{1},\dots,\bm{\xi}_{t})$, and $\bm{\xi}=\bm{\xi}_{[T]}$. The set of uncertain parameters for which $\tau_{i}=t$ is denoted by $\widetilde{\mathcal{I}}_{t}$, and we have $\widetilde{\mathcal{I}}_{t}\cap\widetilde{\mathcal{I}}_{t^{\prime}}=\emptyset$ for all $t\neq t^{\prime}$ and $\mathcal{I}=\bigcup_{t\in\mathcal{T}}\widetilde{\mathcal{I}}_{t}$. The set of uncertain parameters that can materialize in stage $t$ is denoted by $\bar{\mathcal{I}}_{t}$. In the special case where every uncertain parameter can only materialize in one stage, $\bar{\mathcal{I}}_{t}=\widetilde{\mathcal{I}}_{t}$. Similarly, let $\widehat{\mathcal{I}}_{t}$ denote the set of uncertain parameters that can be observed in stage $t$, and $\hat{\tau}_{i}$ and $\tilde{\tau}_{i}$ be the stages between which uncertain parameter $i$ can be observed. Since the observation of an uncertain parameter can only occur after its materialization, we have $\hat{\tau}_{i}\geq\tau_{i}$ and $\tilde{\tau}_{i}\geq\bar{\tau}_{i}$.

The general multistage robust optimization problem with type-1, type-2a, and type-2b endogenous uncertainty can be formulated as follows:

where $\mathcal{Y}_{t}\in\{0,1\}^{|\bar{\mathcal{I}}_{t+1}|}$ and $\mathcal{Z}_{t}\in\{0,1\}^{|\widehat{\mathcal{I}}_{t+1}|}$. The notation is such that $\bm{x}_{[t]}=(\bm{x}_{1},\dots,\bm{x}_{t})$, $\bm{x}=\bm{x}_{[T]}$, $\bm{y}_{[t]}=(\bm{y}_{1},\dots,\bm{y}_{t})$, $\bm{y}=\bm{y}_{[T]}$, $\bm{z}_{[t]}=(\bm{z}_{1},\dots,\bm{z}_{t})$, and $\bm{z}=\bm{z}_{[T]}$. The binary variable $y_{ti}$ equals 1 if uncertain parameter $i$ materializes in stage $t+1$, whereas the binary variable $z_{ti}$ equals 1 if uncertain parameter $i$ is observed in stage $t+1$. We use auxiliary variables $\bm{\bar{z}}_{t-1}=\left(\sum_{t^{\prime}=0}^{t-1}z_{t^{\prime}1},\dots,\sum_{t^{\prime}=0}^{t-1}z_{t^{\prime}K_{[t]}}\right)$ with $K_{[t]}=\sum_{t^{\prime}=1}^{t}K_{t^{\prime}}$ to indicate which uncertain parameters in $\bm{\xi}_{[t]}$ are observed up to stage $t$. The recourse variables in stage $t$, i.e. $\bm{x}_{t}$, $\bm{y}_{t}$, and $\bm{z}_{t}$, are functions of $\bm{\bar{z}}_{t-1}\circ\bm{\xi}_{[t]}$, which represent the uncertain parameters observed up to stage $t$. For notational convenience, we assume that $\bm{\xi}_{1}=\xi_{11}=1$, $\bm{y}_{0}=y_{01}=1$, and $\bm{z}_{0}=z_{01}=1$. The stage-specific uncertainty set $\Xi_{t}$ is defined such that $\Xi_{1}=\{\bm{\xi}_{1}\in\mathbb{R}:\xi_{11}=1\}$, and for $t\geq 2$:

where the polyhedral set directly depends on $\bm{x}_{[t-1]}$ and $\bm{y}_{[t-1]}$, which in turn are functions of observed uncertain parameters given by $\bm{z}_{[t-2]}$. We assume that $\Xi_{t}(\bm{x}_{[t-1]},\bm{y}_{[t-1]},\bm{z}_{[t-2]})\subseteq\{\bm{\xi}_{[t]}\in\mathbb{R}^{K_{[t]}}:\bm{\xi}^{\min}_{[t]}\leq\bm{\xi}_{[t]}\leq\bm{\xi}^{\max}_{[t]}\}$ for all feasible $(\bm{x}_{[t-1]},\bm{y}_{[t-1]},\bm{z}_{[t-2]})$.

The linear constraints in problem (11) include the following inequalities:

Constraints (13a) state that each uncertain parameter $i$ can only materialize between stages $\tau_{i}$ and $\bar{\tau}_{i}$; analogously, uncertain parameter $i$ can only be observed between stages $\hat{\tau}_{i}$ and $\tilde{\tau}_{i}$ according to (13b). Inequalities (13c) ensure that an uncertain parameter can only be observed after it has materialized.

In this section, we present a decision rule approach to (approximately) solve the general multistage robust optimization problem under endogenous uncertainty, which reduces to the two-stage case when $T=2$. The proposed approach is an extension of the method presented in Feng et al. ⁴⁸ and relies on the concept of lifted uncertainty ⁵⁵. Here, the main innovation is the use of auxiliary uncertain parameters to model decision-dependent nonanticipativity.

For ease of exposition and for tractability reasons, we consider the case of fixed recourse, i.e. $\bm{A}_{tt^{\prime}}$, $\bm{D}_{tt^{\prime}}$, and $\bm{H}_{tt^{\prime}}$ do not depend on $\bm{\xi}_{[t]}$. In theory, the presented approach can be adapted to consider random recourse ¹¹, however, at considerable additional computational cost. We further assume that $\bm{b}_{t}(\bm{\xi}_{[t]})=\bm{B}_{t}\bm{\xi}_{[t]}$ and $\mathcal{X}_{t}=\mathbb{R}^{\bar{N}_{t}}\times\{0,1\}^{\widehat{N}_{t}}$. Note that $\bm{x}_{t}$ contain both continuous and binary variables, and we define $\bm{x}_{t}=(\bm{x}^{\mathrm{c}}_{t},\bm{x}^{\mathrm{b}}_{t})$ such that $\bm{x}^{\mathrm{c}}_{t}\in\mathbb{R}^{\bar{N}_{t}}$ and $\bm{x}^{\mathrm{b}}_{t}\in\{0,1\}^{\widehat{N}_{t}}$.