Robust Multistage Optimization with Decision-Dependent Uncertainty

Abstract

Quantified integer (linear) programs (QIP) are integer linear programs with variables being either existentially or universally quantified. They can be interpreted as two-person zero-sum games between an existential and a universal player on the one side, or multistage optimization problems under uncertainty on the other side. Solutions are so called winning strategies for the existential player that specify how to react on moves—certain fixations of universally quantified variables—of the universal player to certainly win the game. In this setting the existential player must ensure the fulfillment of a system of linear constraints, while the universal variables can range within given intervals, trying to make the fulfillment impossible. Recently, this approach was extended by adding a linear constraint system the universal player must obey. Consequently, existential and universal variable assignments in early decision stages now can restrain possible universal variable assignments later on and vice versa resulting in a multistage optimization problem with decision-dependent uncertainty. We present an attenuated variant, which instead of an NP-complete decision problem allows a polynomial-time decision on the legality of a move. Its usability is motivated by several examples.

1 Introduction

Optimization under uncertainty often pushes the complexity of problems that are in the complexity class P or NP, to PSPACE [14]. Nevertheless, dealing with uncertainty is an important aspect of planning and various solution paradigms for optimization under uncertainty exist, e.g. Stochastic Programming [3] and Robust Optimization [2]. In most settings it is assumed that the occurring uncertainty is embedded in a predetermined uncertainty set or that it obeys a fixed random distribution. In particular, planning decisions have no influence on uncertainty. Decision-dependent uncertainty has recently gained importance in both stochastic programming [1, 5, 8, 9] and robust optimization [11, 13, 15, 16]. We focus on quantified integer programming (QIP) [12], which is a robust multistage optimization problem. Only recently, an extension for QIP was presented such that existential and universal variable assignments in early decision stages now can restrain possible universal variable assignments later on and vice versa resulting in a multistage optimization problem with decision-dependent uncertainty [6]. The aim of this paper is to investigate the implications and possibilities of this extension for operations research.

2 Quantified Integer Programs with Interdependent Domains

Quantified Integer Programs (QIP) are Integer Programs (IP) extended by an explicit variable order and a quantification vector that binds each variable to a universal or existential quantifier. Existentially quantified variables depict decisions made by a planner, whereas universally quantified variables represent uncertain events the planner must cope with. In particular, a QIP can be interpreted as a zero-sum game between a player assigning existentially quantified variables against the player fixing the universally quantified variables. The first priority of the so-called existential player is the fulfillment of the existential constraint system A ^∃x ≤ b ^∃ when all variables x are fixed. A solution of a QIP is a strategy for assigning existentially quantified variables, that specifies how to react on moves of the universal player—i.e. assignments of universally quantified variables—to certainly fulfill A ^∃x ≤ b ^∃. By adding a min-max objective function the aim is to find the best strategy [12].

Definition 1 (Quantified Integer Program)

Let $A^\exists \in \mathbb {Q}^{m_\exists \times n}$ and $b^\exists \in \mathbb {Q}^{m_\exists }$ for $n,m_\exists \in \mathbb {N}$ and let $\mathcal {L}=\{x \in \mathbb {Z}^n \mid x \in [l,u]\}$ with $l, u \in \mathbb {Z}^n$. Let Q ∈{∃, ∀}ⁿ be a vector of quantifiers. We call each maximal consecutive subsequence in Q consisting of identical quantifiers a quantifier block and denote the i-th block as B _i ⊆{1, …, n} and the corresponding quantifier by Q ⁽ⁱ⁾ ∈{∃, ∀}, the corresponding variables by x ⁽ⁱ⁾ and its domain by $\mathcal {L}^{(i)}$. Let $\beta \in \mathbb {N}, \beta \leq n$, denote the number of blocks. Let $c \in \mathbb {Q}^n$ be the vector of objective coefficients and let c ⁽ⁱ⁾ denote the vector of coefficients belonging to block B _i. Let $Q \circ x \in \mathcal {L}$ with the component wise binding operator ∘ denote the quantification vector $(Q^{(1)}x^{(1)} \in \mathcal {L}^{(1)}, \ldots , Q^{(\beta )} x^{(\beta )} \in \mathcal {L}^{(\beta )})$ such that every quantifier Q ⁽ⁱ⁾ binds the variables x ⁽ⁱ⁾ of block i to its domain $\mathcal {L}^{(i)}$. We call

$$\displaystyle \begin{aligned} {\min\limits_{x^{(1)} \in \mathcal{L}^{(1)}}\left( c^{(1)}x^{(1)}+ \max\limits_{x^{(2)} \in \mathcal{L}^{(2)}} \left( c^{(2)}x^{(2)} + \ldots \min\limits_{x^{(\beta)} \in \mathcal{L}^{(\beta)}} c^{(\beta)} x^{(\beta)}\right)\right)} \end{aligned}$$

$$\displaystyle \begin{aligned}\text{s.t.}\quad Q \circ x \in \mathcal{L}:\ A^\exists x \leq b^\exists \end{aligned}$$

a QIP with objective function (for a minimizing existential player).

In the above setting the universally quantified variables only must obey the hypercube $\mathcal {L}$ given by the variable bounds. Hence, QIPs are rather unsymmetric as—even though the min-max semantics is symmetrical—only the existential player has to deal with a polytope (given by A ^∃x ≤ b ^∃) the universal player can modify. In [7] this setting was extended to allow a polyhedral domain for the universal variables given by a second constraint system A ^∀x ≤ b ^∀. However, still the existential player’s variables had no influence on this system. Only recently, a further extension was presented allowing the interdependence of both variable domains [6]. The presented Quantified Integer Program with Interdependent Domains (QIP^ID) required the definition of a legal variable assignment, since now the case that both constraint systems are violated could occur and the player who made the first illegal move loses (we refer to [6] for more details).

Definition 2 (Legal Variable Assignment)

For variable block i ∈{1, …, β} the set of legal variable assignments $\mathcal {F}^{(i)}(\tilde {x}^{(1)},\ldots ,\tilde {x}^{(i-1)})$ depends on the assignment of previous variable blocks $\tilde {x}^{(1)},\ldots ,\tilde {x}^{(i-1)}$ and is given by

$$\displaystyle \begin{aligned}{{ \mathcal{F}^{(i)} = \left\lbrace \hat{x}^{(i)}\in \mathcal{L}^{(i)} \left\vert \ \exists x=(\tilde{x}^{(1)},\ldots,\tilde{x}^{(i-1)},\hat{x}^{(i)},x^{(i+1)},\ldots,x^{(\beta)}) \in \mathcal{L} : \right. A^{Q^{(i)}}x \leq b^{Q^{(i)}} \right\rbrace } } \end{aligned}$$

i.e. after assigning the variables of block i there still must exist an assignment of x such that the system of Q ⁽ⁱ⁾ ∈{∃, ∀} is fulfilled. The dependence on the previous variables $\tilde {x}^{(1)},\ldots ,\tilde {x}^{(i-1)}$ will be omitted when clear.

Hence, even a local information—whether a variable is allowed to be set to a specific value—demands the solution of an NP-complete problem. Just like QIP, QIP^ID is PSPACE-complete [6].

Definition 3 (QIP with Interdependent Domains (QIP^ID))

For given A ^∀, A ^∃, b ^∀, b ^∃, c, $\mathcal {L}$ and Q with $\{x \in \mathcal {L} \mid A^\forall x\leq b^\forall \} \neq \emptyset$ we call

$$\displaystyle \begin{aligned}\min\limits_{x^{(1)} \in \mathcal{F}^{(1)}} \left(c^{(1)}x^{(1)}+ \max\limits_{x^{(2)} \in \mathcal{F}^{(2)}} \left( c^{(2)}x^{(2)}+ \ldots \max\limits_{x^{(\beta)} \in \mathcal{F}^{(\beta)}} c^{(\beta)}x^{(\beta)}\right)\right) \end{aligned}$$

$$\displaystyle \begin{aligned}\text{s.t.} \quad \exists x^{(1)} \in \mathcal{F}^{(1)}\ \forall x^{(2)} \in \mathcal{F}^{(2)} \ldots\ \forall x^{(\beta)} \in \mathcal{F}^{(\beta)}: \ A^\exists x \leq b^\exists \end{aligned}$$

a Quantified Integer Program with Interdependent Domains (QIP^ID).

We say a player q ∈{∃, ∀} loses, if either a) $A^q \tilde x \nleq b^q$ for a fully assigned $\tilde {x}$ or b) if there exists no legal move for this player at some point during the game, i.e. $\mathcal {F}^{(i)}=\emptyset$. As we will see in the following section, a general QIP^ID is too comprehensive for most problems of the OR-world and a few restrictions are sufficient in order to simplify the solution process.

3 Addition Structural Requirements for A ^∀x ≤ b ^∀

The recurring NP-complete evaluation of $\mathcal {F}^{(i)}$ constitutes a massive overload when solving a QIP^ID via game-tree search [4]. In a general QIP^ID it can occur that the universal player has no strategy in order to ensure the fulfillment of A ^∀x ≤ b ^∀. This makes sense in an actual two-person game where both players could lose. In an OR-setting, however, the universal player can be considered to be the one who decides which uncertain event will occur, the scope of which depends on previous planning decisions. But obviously there exists no planning decision that obliterates uncertainty in the sense that there is no further legal assignment for universal variables such that uncertainty “loses”. Therefore, we make the following assumptions:

• a) For each universal variable block i ∈{1, …, β} we demand

  $\forall \ \left (\hat x^{(1)} \in \mathcal {L}^{(1)}, \hat x^{(2)} \in \mathcal {F}^{(2)}, \ldots ,\hat x^{(i-2)} \in \mathcal {F}^{(i-2)}, \hat x^{(i-1)}\in \mathcal {L}^{(i-1)} \right ): \mathcal {F}^{(i)} \neq ~\emptyset \ .$

• b) Let i ∈{1, …, β} with Q ⁽ⁱ⁾ = ∀ and let $\hat {x}^{(1)} \in \mathcal {L}^{(1)}, \ldots , \hat {x}^{(i-1)} \in \mathcal {L}^{(i-1)}$ be a partial variable assignment up to block i. If $\tilde {x}^{(i)} \not \in \mathcal {F}^{(i)} ( \hat {x}^{(1)}, \ldots , \hat {x}^{(i-1)} )$ then

  $$\displaystyle \begin{aligned} \exists k \in \{1,\ldots,m_\forall\}: \sum_{j<i} A_{k,(j)}^\forall \hat{x}^{(j)} + A^\forall_{k,(i)}\tilde{x}^{(i)} + \sum_{j>i} \min_{x^{(j)}\in \mathcal{L}^{(j)}} A^\forall_{k,(j)} x^{(j)} \nleq b^\forall \ . \end{aligned}$$

Restriction a) requests, that there always exists a legal move for the universal player, even if the existential player does not play legally. In particular, previous variable assignments—although they can restrict the set of legal moves— can never make A ^∀x ≤ b ^∀ unfulfillable. In b) we demand that a universal variable assignment $\tilde {x}^{(i)} \in \mathcal {L}^{(i)}$ is illegal, if there is a universal constraint that cannot be fulfilled, even in the best case. Therefore, it is sufficient to check separately the constraints in which $\tilde {x}^{(i)}$ is present in order to ensure $\tilde {x}^{(i)} \in \mathcal {F}^{(i)}$. Hence, there always exists a strategy for the universal player to fulfill A ^∀x ≤ b ^∀ (due to a)) and further checking $x^{(i)} \in \mathcal {F}^{(i)}$ can be done in polynomial time (due to a) and b)) for universal variables. The legality of existential variable assignments does not have to be checked immediately (due to a)) and can be left to the search.

4 Application Examples

In this section we briefly describe a few examples where QIP^ID can be used in order to grasp the relevance of multistage robust optimization with decision-dependent uncertainty. We will not explicitly specify how the described problems can be translated into linear constraints, but note, that all the upcoming examples can be modeled as QIP^ID while meeting the requirements described in Sect. 3. Further, keep in mind that QIP^ID is a multistage optimization framework. Therefore, rather than adhering to adjustable robust programming with only a single response stage, planning problems with multiple decision stages are realizable.

Maintenance Reduces Downtime

Consider a job shop problem with several tasks and machines. One is interested in a robust schedule as machines can fail for a certain amount of time (universal variables indicate which machines fail and how long they fail). The basic problem can be enhanced by adding maintenance work to the set of jobs: the maintenance of a machine prevents its failure for a certain amount of time at the expense of the time required for maintenance and the maintenance costs. Therefore, the universal constraint system contains constraints describing the relationship between maintenance and failure: With existential variable m _i,t indicating the maintenance of machine i at time t and universal variable f _i,t indicating the failure of machine i at time t the (universal) constraint f _i,t+j ≤ 1 − m _i,t prohibits the failure of machine i for each of the j ∈{0, …, K} subsequent time periods. The universal constraint system also could contain further restrictions regarding the number of machines allowed to fail at the same time, analogous to budget constraints common in robust optimization [15]. This budget amount also can depend on previous planning decisions, e.g. the overall machine utilization. Further, reduced operation speed can reduce wear and therefore increase durability and lessen the risk of failure.

Workers’ Skills Affect Sources of Uncertainty

The assignment of employees to various tasks may have significant impact on potential occurring failures, processing times and the quality of the product. For example, it might be cheaper to have a trainee carry out a task, but the risk of error is higher and the processing time might increase. Further, some worker might work slower but with more diligence—resulting in a long processing-time but a high quality output—than other faster, but sloppier, workers. Hence, the decision which worker performs a particular task has an impact on the anticipated uncertain events. In a more global perspective staff training and health-promoting measures affect the skills and availability of a worker, and thereby affecting potential risks.

Road Maintenance for Disaster Control

In order to mitigate the impact of a disaster, road rehabilitation can improve traveling time as the damage of such roads can be reduced (see [13]). Again, a budget for the deterioration of travel times for all roads could be implemented, whereat the budget amount could be influenced by the number of emergency personal, emergency vehicles and technical equipment made available.

Time-Dependent Factors in Process Scheduling

In [10] the authors present a process scheduling approach with uncertain processing-time of the jobs, whereat the range of the uncertain processing-time parameters depend on the scheduling time of the job itself. The selection of specific scheduling times therefore actively determines the range in which the uncertain processing-times are expected. For a QIP this influence on uncertainty could be achieved by adding universal constraints as follows: Let x _i,t be the (existential) binary indicator whether task i is scheduled to start at time t and let y _i be the (universal) variable indicating the occurring processing-time of task i. Let l _i,t and u _i,t indicate the range of the processing-time of task i if scheduled at t. Adding ∑_tl _i,tx _i,t ≤ y _i ≤∑_tu _i,tx _i,t to the universal constraint system would establish the intended interdependence.

5 Conclusion

We addressed the largely neglected potential of optimization under decision-dependent uncertainty. In the scope of quantified integer programming with decision-dependent uncertainty we presented reasonable restrictions such that a game-tree search algorithm must not cope with recurring NP-complete subproblems but rather polynomial evaluations. Further, we provided several examples where such a framework is applicable.