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 Ax ≤ 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 (x1 and x2) 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 x1 and x2 are set to 1 the universal variable must not be 1. However, the existential player also has to ensure that setting x1 and x2 to 1 will no render the existential constraint system violated. As this is not the case, x1=1 and x2=1 is a legal variable assignment. In this case setting x3=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 and its name has to start with "U_" [Download instance]. Also, below the instance is given. Note that unnamed constraints, and named constraints not starting with "U_" are considered existential constraints.


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

527efb333