A universal constraint system: Allowing polyhedral and
decisiondependent uncertainty
A QIP is inherently asymmetric, as even though the minmax
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 decisiondependent, uncertainty set
can only be modeled
via tricky and not straightforward modeling techniques. In
order to be able to model the uncertainty
set in a more simple
way a second constraint system
A^{∀}x ≤ b^{∀}
was introduced, which allowed to explicitly
model a polyhedral
uncertainty set [1]. The usage of this universal constraint
system was later extended to even allow decisiondependent
uncertainty set [2]. For both modeling frameworks we also
extended our solution framework [3].
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 nonzero
entries in the universal constraint
system this instance is a
QIP with decisiondependent 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.
Policy Space
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 NPcomplete problem.
We formalized this observation and we call instances
those observations apply to simply restricted.
Definition Simply Restricted
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.

[1] 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
[2] 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
[3] M. Hartisch.
Quantified Integer Programming with
Polyhedral and DecisionDependent Uncertainty.
PhD thesis, University of Siegen, Germany, 2020


Downloads
Yasol for Mac OS
Yasol for Linux
Yasol for Windows
Instances
