Test instances
In order to get fun with Yasol, you need some input instances in qlp file format. Here you can find a collection of test instances.
Artificial QIP instances
Quantified Integeger Programs (QIP) are Q-MIPs with only integer variables. A special case of QIPs are Quantified Boolean Programs (QBP) with only boolean variables. The constraints are linear and an objective typically exists.
Combinatorial QIP instances
Detailed information about the following QIP instances can be found in this Ph.D. thesis or this preprint.
Robust Multistage Selection Problem
The task is to select p out of n=2p items, such that the costs are minimized. This happens in a multistage manner: In a first (existential) decision stage items can be selected for fixed costs. Then, in a universal decision stage, one of N cost scenario is selected and in the subsequent existential decision stage further items can be selected. Those two stages (disclosure of a scenario and selection of items) are repeated S times. We provide two different quantified models: a standard QIP and a QIP with universal constraints, i.e. a QIP with polyhedral uncertainty set. Selection instances have the naming scheme selection-n-p-N-S-R-t.qlp. R is the seed for the random number generator. t∈{s,u} represents the model type: s for "standard QIP" and u for "QIP with universal constraints". We provide the following testsets:
- N=4, n∈{10,20,30,40,50} and S∈{1,..,8}. 50 instances per constellation:
- Download: 2000 QIP instances
- Download: 2000 QIP instances with universal constrains
- n=10, N=2^k, k∈{1,..,8} and S=s∈{1,..,8} with k+s≤11. 50 instances per constellation:
- Download: 2450 QIP instances
- Download: 2450 QIP instances with universal constrains
Robust Multistage Assignment Problem
For a weighted bipartite graph G=(V,E,c) with V=A∪B, n=|A|=|B| one wants to determine a perfect matching of minimum costs. Similar to the selection problem, this happens in a multistage manner: In a first (existential) decision stage edges can be selected for fixed costs. Then, in a universal decision stage, one of N cost scenario is selected and in the subsequent existential decision stage further edges can be selected. Those two stages (disclosure of a scenario and selection of edges) are repeated S times. Again, we provide two different quantified models: a standard QIP and a QIP with universal constraints. Assignment instances have the naming scheme selection-n-N-S-R-t.qlp. R is the seed for the random number generator. t∈{s,u} represents the model type: s for "standard QIP" and u for "QIP with universal constraints". We provide the following testset:
- n∈{4,5,6,7,8,9,10}, N∈{2,4,8} and S∈{1,2,3,4}. 50 instances per constellation:
- Download: 4200 QIP instances
- Download: 4200 QIP instances with universal constrains
Runway Scheduling Instances
For a set of airplanes A, a set of timeslots S, and b runways we are interested in a b-matching such that each airplane is assigned to exactly one time slot and each time slot contains at most b airplanes. After an initial plan is determined, the time windows (a set of time slots) for a (sub)set of airplanes are disclosed. These airplanes must be assigned to their final time slot (within the given time window). This happens in a multistage manner with s being the number of disclosures, i.e. the number of universal variable blocks, e.g. s=2 stands for the quantification sequence ∃ ∀ ∃ ∀ ∃. The universal player is restricted in the way she is allowed to select the time windows: the overall time window lengths must exceed a given value. This can be modeled either explicitly by using universal constraints or implicitly by adding variables and constraint that detect and penalize such a violation. For a more thorough introduction we refer to this Ph.D. thesis or this site. Runway scheduling instances have the naming scheme RWS-|A|-b-|S|-s-R-t.qlp. Again, R is the seed for the random number generator. t∈{s,u} represents the model type: s for "standard QIP" and u for "QIP with universal constraints". We provide the following testsets:
- |A|∈{2,...,8}, |S|∈{3,...,10}, b∈{2,3,4} with s=1. 20 instances per constellation:
- Download: 3360 QIP instances
- Download: 3360 QIP instances with universal constrains
- |A|=7, |S|=12, b=3 and s∈{1,..,4}. 300 instances per constellation:
- Download: 1200 QIP instances
- Download: 1200 QIP instances with universal constrains
Other instances
The Quantified Satisfiability problem (QSAT), which is also know as the satisfiability of Quantified Boolean Formulas (QBF), is related to the Q-MIP-problem. In QSAT there is no objective function and all variables are binary. Further, it deals with clauses instead of arithmetic linear inequalities. However, with some effort and good will, it is possible to extract very special QMIPs from QSAT instances. Similar is the situation with MIPs, which deal with linear constraints but without quantification.
Here, we present some further examples from these two sub-disciplines, collected from qbflib.org and miplib and converted to QLP-format.
Please note that not all instances have been converted 1:1 due to some border cases in the conversion.