Q-MIPs

Quantified (Mixed) Integer Linear Programming

Mixed-integer linear programming (MIP) is a well-established state-of-the-art technique for computer-aided optimization. However, companies observe an increasing danger of disruptions that prevent them from acting as planned. One reason is that input data is often assumed to be deterministic, but in reality, they are afflicted with uncertainties which cannot be adequately described in MIPs, often. This is the point where Q-MIPs are intended to support future modeling.

In 2007, Subramani coined the terms Quantified Linear Program and Quantified Integer Program and thus extended the traditional notions of Linear and Integer Programming¹. The resulting quantified programs are both a strong modelling language and an intuitive input to next generation optimization software.

We extended this notion one step further and introduced a minimax objective²:

\(\textbf{Definition}~\text{(Quantified Linear Program (QLP))}\). Let there be a vector \(x = (x_1,...,x_n)^T \in \mathbb{Q}^n\) of variables, integral lower and upper bounds \(l \in \mathbb{Z}^n\) with \(l_i \leq x_i \leq u_i\), a coefficient matrix \(A \in \mathbb{Q}^{m \times n}\), a righthand side vector \(b \in \mathbb{Q}^m\) and a vector of quantifiers \(Q = (Q_i, ..., Q_n)^T \in \left\{\forall, \exists \right\}^n\), let the term \(Q \circ x \in \left[ l,u \right]\) with the component-wise binding operator \(\circ\) denote the quantification vector \((Q_1x_1 \in \left[ l_1,u_1 \right], ..., Q_nx_n \in \left[ l_n, u_n \right])^T\) such that every quantifier \(Q_i\) binds the variable \(x_i\) ranging over the interval \(\left[ l_i, u_i \right]\). Each maximal consecutive subsequence of \(Q\) consisting of identival quantifiers is called a quantifier block - the corresponding subsequence of \(x\) is called a variable block, with the \(i\)-th block being denoted by \(x^{i}\). Let there also be a vector of objective coefficients \(c \in \mathbb{Q}^n\). We call \((Q, l, u, A, b, c)\) with

\[\begin{align} z = \min_{x^1}(c^1x^1 + \max_{x^2}(c^2x^2 + &\min_{x^3}(c^3x^3 + \max_{x^4}(... \min_{x^m} c^mx^m)))) \\[5pt] Q \circ x \in &\left[ l, u \right]: Ax \leq b \end{align}\]

a quantified linear program (QLP) with objective function.

... as well as a restricted mixed version with the following attributes:

the objective is minmax (more exactly: min max min … max min max) and is linear for any single game
integer variables are allowed on all exist-stages
(only) binary variables are allowed on universal stages
continuous variables are allowed (only) on the last stage, assuming it is an existential stage
quantifiers are either existential or universal

¹ K. Subramani: On a decision procedure for quantified linear programs. Ann. Math. Artif. Intell. 51(1): 55-77 (2007)
² U. Lorenz, J. Wolf: Solving Multistage Quantified Linear Optimization Problems with the Alph-beta nested Benders Decomposition, EURO Journal on Computational Optimization, pp. 349 - 370, Springer 2015

A tiny Q-MIP

Let \(x_1\) and \(x_3\) be existential variables and \(x_2\) a universal variable. Thus we have, \(\exists x_1~ \forall x_2~ \exists x_3\). The aim is to find an optimal first stage setting for \(x_1\) such that the objective

\[ \max_{x_1}(x_1 + \min_{x_2}(x_2 + \max_{x_3}(x_3))) \]

is optimized, and such that

\[\begin{align} -2x_2 - x_3 &\leq -2 \\[5pt] -x_1 + 2x_2 + x_3 &\leq 2 \\[5pt] 2x_1 + 4x_2 &\leq 6 \\[10pt] 0 \leq x_1 \leq 2 \\[5pt] 0 \leq x_2 \leq 1 \\[5pt] 0 \leq x_3 \leq 2 \end{align}\]

Let \(x_1\) be integer, \(x_2\) binary, and \(x_3\) be continuous.

Then the objective value is 3 and the optimal assignment of \(x_1\) is 1. Moreover, \(x_3\) should be set to either 0 or 2, depending on whether \(x_2\) becomes 1 or 0. It is possible to visualize the policy. In the following picture, you see an outer 3d-polytope which is caught in a box. That is the polytope which is generated by the existential LP-relaxation, i.e. all variables are assumed to be existential and continuous. Within the given polytope you see another one, in light red. That is the union of all 3D-points that are part of any feasible policy of the existential player, given the original \(\exists~\forall~\exists\) quantifier string. You can also see that \(x_1\) can be set between 0 and 1 (i.e. half of the box in \(x_1\)-direction) and depending on how \(x_2\) is set (either 0 or 1), \(x_3\) can be moved up to its upper bound 2 or must smaller or equal to 1.

You can download the QLP file for this instance. For a closer look at the file format see this page.

A universal constraint system: Allowing polyhedral and decision-dependent uncertainty

A QIP is inherently asymmetric, as even though the min-max semantic of the objective is symmetric, the universally quantified variables are only restricted to their domain (solely given by bounds), whereas the existential player—in addition to having to obey the variable bounds—also must ensure the fulfillment of the constraint system. In other words: only the existential player has to cope with a polytope influenced by the opponent’s decisions whereby a polyhedral, or even decision-dependent, uncertainty set can only be modeled via tricky and not straight-forward modeling techniques. In order to be able to model the uncertainty set in a more simple way a second constraint system \(A^\forall x \leq b^\forall\) was introduced, which allowed to explicitly model a polyhedral uncertainty set¹. The usage of this universal constraint system was later extended to even allow decision-dependent uncertainty set². For both modeling frameworks we also extended our solution framework³.

Example:
We consider a binary quantified program with an existential and a universal constraint system. As existentially quantified variables (\(x_1\) and \(x_2\)) have non-zero entries in the universal constraint system this instance is a QIP with decision-dependent uncertainty called QIP with interdependent domains. In particular, if both \(x_1\) and \(x_2\) are set to 1 the universal variable must not be 1. However, the existential player also has to ensure that setting \(x_1\) and \(x_2\) to 1 will no render the existential constraint system violated. As this is not the case, \(x_1 = 1\) and \(x_2 = 1\) is a legal variable assignment. In this case setting \(x_3=1\) would be an illegal assignment by the universal player, as it irrevocably violated the universal constraint system.

\[\begin{align} c^Tx &: \min x_1-2x_2+2x_3+x_4 \\[5pt] Q \circ \mathcal{L} &: \exists x_1 \in \left\{0, 1 \right\} \exists x_2 \in \left\{0, 1 \right\} \forall x_3 \in \left\{0, 1 \right\} \exists x_4 \in \left\{0, 1 \right\} \\[5pt] A^\exists x \leq b^\exists &: \begin{pmatrix} 1 & -2 & 1 & -1 \\ 1 & 1 & 1 & -1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ \end{pmatrix} \leq \begin{pmatrix} 1 \\ 2 \end{pmatrix} \\[5pt] A^\forall x \leq b^\forall &: \begin{pmatrix} 1 & 1 & 1 & 0 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ \end{pmatrix} \leq \begin{pmatrix} 2 \end{pmatrix} \end{align}\]

The optimal solution of this instance is -1 with principal variation (1,1,0,0). In order to solve this instance with our solver, a universal constraint must be explicitly named in the QLP file using the keyword UNCERTAINTY SUBJECT TO [Download instance].

MINIMIZE
x1 -2x2 +2x3 +x4
SUBJECT TO
x1 -2x2 +x3 -x4 <= 1
x1 +x2 +x3 -x4 <= 2
UNCERTAINTY SUBJECT TO
x1 +x2 +x3 <= 2
BOUNDS
0 <= x1 <= 1
0 <= x2 <= 1
0 <= x3 <= 1
0 <= x4 <= 1
BINARIES
x1 x2 x3 x4
EXISTS
x1 x2 x4
ALL
x3
ORDER
x1 x2 x3 x4
END

Simply Restricted Instances:
In order to ensure that universal variable assignments are legal, i.e. that they do not eventually result in a violation of the universal constraint system, the feasibility of the universal constraint system must be checked in each step. This can be tedious as this means solving an IP at each universal decision node. However, we observed the following in many multistage robust problems:

Uncertainty maybe can be manipulated, but it cannot be 'defeated' in the sense that no legal move remains.
Potential realizations of uncertain parameters are easily recognizable, i.e. classifying a universal variable assignment as legal or illegal should not be an NP-complete problem.

We formalized this observation and we call instances those observations apply to simply restricted.

\(\textbf{Definition}~(\text{Simply Restricted}~QIP^{ID})\). Let \(P = (A^\exists, A^\forall, b^\exists, b^\forall, c, \mathcal{L}, Q)\) be a \(QIP^{ID}\). If the two following conditions are fulfilled, we call \(P\) a simply restricted \(QIP^{ID}\).

For each universal variable block \(i \in \mathcal{A}\) we demand

\[\begin{equation*} \forall~ (\hat{x}^{(1)}\in \mathcal{L}^{(1)}, \hat{x}^{(2)} \in \mathcal{F}^{(2)}, ..., \hat{x}^{(i-2)} \in \mathcal{F}^{(i-2)}, \hat{x}^{(i-1)} \in \mathcal{L}^{(i-1)}): \mathcal{F}^{(i)} \neq \emptyset. \end{equation*}\]

Let \(i \in \mathcal{A}\) and let \(\hat{x}^{(1)} \in \mathcal{L}^{(1)}, ..., \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)}, ..., \hat{x}^{(i-1)})\), then

\[\begin{equation*} \exists ~ k \in \left\{ 1, ..., m_\forall \right\}: \sum_{j < i} A_{k,(j)}^\forall \hat{x}^{(j)} + A_{k,(i)}^\forall \tilde{x}^{(i)} + \sum_{j>i} \min_{x^{(j)} \in \mathcal{L}^{(j)}} A_{k,(j)}^\forall x^{(j)} \not \leq b_k^\forall. \end{equation*}\]

The benefit of having a simply restricted instance is that then the legality of a universal variable assignment can be checked be simply traversing the universal constraints and checking whether they remain satisfiable, even in the worst case. Thus, the satisfiability of entire universal constraint system can be checked locally rather than solving the entire IP. If your instance is simply restricted you can specify "isSimplyRestricted=1" in the Yasol.ini file. If your instance does not fulfill the requirements, or if you are not sure, simply set "isSimplyRestricted" to zero, and each universal variable assignment will be verified by solving the corresponding universal IP.

¹ M. Hartisch, T. Ederer, U. Lorenz, J. Wolf. Quantified Integer Programs with Polyhedral Uncertainty Set. In: A. Plaat, W. Kosters, J. van den Herik (eds) Computers and Games. CG 2016. Lecture Notes in Computer Science, vol 10068. Springer, Cham, 2016
² M. Hartisch, U. Lorenz. Mastering uncertainty: Towards robust multistage optimization with decision dependent uncertainty. In 16th Pacific Rim International Conference on Artificial Intelligence, PRICAI 2019, Seiten 446–458. Springer, 2019
³ M. Hartisch. Quantified Integer Programming with Polyhedral and Decision-Dependent Uncertainty. PhD thesis, University of Siegen, Germany, 2020

Quantified Programs applied to Runway Scheduling

The following QIP problem definition and, as a consequence the content of this page, is a result of cooperative work between University Siegen (S. Gnad, M. Hartisch, U. Lorenz) and FAU Erlangen (L. Hupp, F. Liers, A. Peter). We used QIPs to model and solve a matching problem that can be interpreted as an airplane scheduling problem in which each airplane must be assigned to a time slot and at most b airplanes can be assigned to one time slot. This b-matching is enhanced by uncertain time intervals in which an airplane must land. For reasons of simplicity we will use the airplane scheduling interpretation to explain our intentions.

Example_1 — Figure: Example with 4 airplanes and 6 possible time slots. 2 airplanes can be scheduled at each time slot (b=2). The initial planning costs are given and the possible time windows (consisting of two time slots) for each airplane are depicted as sliders below.

Broadly speaking, we are interested in an initial plan that can be fixed cheaply if the mandatory time windows (the sliders in the figure) for some planes do not contain the initially scheduled time slot. Reasons for such variations (in the arrival time) might be adjusted airspeed (due to weather) or operational problems.

The incurred costs are composed of the costs for the initial plan and the fixing costs. The costs for the initial plan only depend on the the initial assignment of planes to time slots regarding predetermined costs: In the example above assigning airplane 2 to time slot 4 would result in costs of 2 monetary units.

There are some ideas for the composition of the fixing costs, for example:

rescheduling one airplane results in a fixed fee
rescheduling one airplane results in costs depending on the newly selected time slot
rescheduling one airplane results in costs depending on the initial and the newly selected time slot

For simplicity and a more general presentation, the costs of replacing airplane i depend on a function \(f(x_{i^*},y_{i^*})\) representing the relation between initial plan, fixed plan and fixing costs. Depending on the selected cost type, this function can be modeled using linear constraints.

Basic quantified program for the airplane runway scheduling problem:

\[\begin{align} \min \quad & \sum_{i \in A}\sum_{j \in W} c_{i,j}x_{i,j} + \max \left\{ \min \left\{ \sum_{i \in A} c_i^{fix} \right\} \right\} \\ \mathrm{s.t.} \quad & \exists X \in \left\{0, 1 \right\}^{\left| A \right| \times \left| W \right|} \\ & \forall S \in \mathcal{S}, L \in \mathcal{L} \\ & \exists Y \in \left\{0, 1 \right\}^{\left| A \right| \times \left| W \right|}: \\ & \sum_{j \in W} x_{i,j} = 1 \quad && \forall i \in A \\ & \sum_{i \in A} x_{i,j} \leq b \quad && \forall j \in W \\ & \sum_{j \in W} y_{i,j} = 1 \quad && \forall i \in A \\ & \sum_{i \in A} y_{i,j} \leq b \quad && \forall j \in W \\ & s_i \leq \sum_{j \in W} j \cdot y_{i,j} \leq s_i+l_i \quad && \forall i \in A \\ & c_i^{fix} = f(x_{i,*}, y_{i,*}) \quad && \forall i \in A \\ \end{align}\]

Brief explanation of the model:

three stage objective function
- first stage: select initial plan resulting in initial costs
- second stage: uncertain events → new conditions regarding allowed time slots (the start \((s_i \in S)\) and the length \((l_i \in L)\) of the time window is selected for each airplane \(i\))
- third stage: if necessary fix the initial plan causing additional costs
First stage existential variables: Initial scheduling variables
Second stage universal variables: Specification of the starting point (\(s\)) and the length (\(l\)) of the mandatory time window for each airplane
Third stage existential variables: Final scheduling variables respecting the time windows defined in stage two
Ensures that each airplane is assigned to exactly one time slot in the initial plan
Ensures that each time slot can only hold b airplanes in the initial plan
Ensures that each airplane is assigned to exactly one time slot in the fixed plan
Ensures that each time slot can only hold b airplanes in the fixed plan
Binds the assigned time slots of the fixed plan to the given time window
Fixing costs depend on difference between initial plan (\(X\)) and fixed plan (\(Y\)); various cost models imaginable.

Example costs: fixed fee
If, for example, the first mentioned fixing costs were used, i.e. fixed fee for replanning, further existential variables \(Z \in \left\{0,1\right\}^{\left|A\right| \times \left|W\right|}\) are installed in the third stage and the following constraints would be added:

\[\begin{align} Z \in \left\{0,1\right\}^{\left|A\right| \times \left|W\right|} \\[8pt] z_{i,j} \geq y_{i,j} - x_{i,j} \quad &\forall i \in A, j \in W \\[8pt] c_i^{fix} = \sum_{j \in W} fz_{i,j} \quad &\forall i \in A \end{align}\]

In this case variable \(z_{i,j}\) must identify if airplane \(i\) was not scheduled in time slot \(j\) in the initial plan but in the fixed plan resulting in costs \(f\) for this plane.

Restricting the universal variables:
By choosing the domains of the universal variables \(S\) and \(L\) carefully the user already can limit the influence of the universal variables. Nevertheless, some scenarios should not be considered: For example one might want to allow the time windows for some airplane to consist of only one time slot. However, this should not be the case for all airplanes, since this would constitute a rather implausible event. One conceivable demand for the time windows could be that on average the time windows have a length of 2 (i.e. consist of two time slots). Thus, the universal variables L should not only be forced to lie within some bounds, but also within a specific polytope. The polytope for this example would require the following additional constraint:

\[ \frac{1}{\left|A\right|}\sum_{i \in A}l_i \geq 2 \]

However, simply adding this constraint to the constraint system would not have the desired effect. In fact, it would increase the influence of the universal variables since this constraint could easily be violated and thus the entire instance would become infeasible. However, adding this as a universal constraint would do the trick. or the enforcement of rules regarding the universal variables could be performed implicitly: In a final existential block the fulfillment of such a constraint is checked and if a violation is detected the remaining constraint system is relaxed and the objective value is reduced dramatically. This has the effect that a violation provoked by the allocation of universal variables results in a very good objective value (regarding the existential objective of minimization) and is thus unfavorable with respect to the universal maximization objective.

Instances:
For this runway scheduling problem we created several instances with several variations:

Instances with more than 3 stages: After the initial plan the time windows for some airplanes are selected by the universal variables. For these airplanes a fixed plan must be prepared. After that the time windows for the remaining airplanes are specified by the universal variables and once again the plan must be fixed.
Instances with restricted universal variables: As explained above, the universal variables determining the interval lengths must obey some rules.
Instances with different objective function: the first (fixed fee) and third (distance from initial and final time slot) presented fixing costs are considered.
Instances with diverse time windows: The interval length can vary from 0 up to 4 time slots and the interval itself can start at up to 4 time slots.
Instances with different numbers of airplanes and time slots: the number of airplanes varies between 5 and up to more than 100. The number of time slots varies between 7 and up to 200 time slots.

Download Instances

For each of these 29 instances our solver Yasol (utilizing the Cplex LP solver) had one hour to solve the instance. The results where compared to Cplex trying to solve the corresponding deterministic equivalent program, also within one hour. The results are displayed in the following table. Yasol solves 25 out of the 29 instances while CPLEX only can solve 6 of the converted DEPs. Even when only considering the instances solved by CPLEX, Yasol only needs 2.66 seconds on average compared to 6.83 seconds. If instances get large (easy indicator is the number right after the 'A' in the instance name) Yasol is able to detect infeasible instances rather fast but does not manage to grasp optimal feasible solutions. CPLEX, on the other hand, often exceeds the available memory on such instances and does not cope very well if many universal variables are present. But even on instances with few universal variables CPLEX quickly reaches its limit.

Upload_Table

¹ Hartisch M., Ederer T., Lorenz U., Wolf J. (2016) Quantified Integer Programs with Polyhedral Uncertainty Set. In: Plaat A., Kosters W., van den Herik J. (eds) Computers and Games. CG 2016. Lecture Notes in Computer Science, vol 10068. Springer, Cham