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^∀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 decision-dependent 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₁ and x₂) 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₁ and x₂ are set to 1 the universal variable must not be 1. However, the existential player also has to ensure that setting x₁ and x₂ to 1 will no render the existential constraint system violated. As this is not the case, x₁=1 and x₂=1 is a legal variable assignment. In this case setting x₃=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 NP-complete 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 Decision-Dependent Uncertainty. PhD thesis, University of Siegen, Germany, 2020