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.
Multistage Robust Selection Problem
The task is to select p out of n=2p items, such that the costs are minimized^{1 2}. 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
Multistage Robust 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^{1 2}. 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
Multistage Robust Lot-Sizing Problem
We consider a single item lot-sizing problem with discrete ordering decisions and T periods^{2}. At the beginning of each time period, the product demand that needs to be satisfied is disclosed: Either d_{t} or d_{t}. In order to serve the demand, in each period t∈{0,...,T-1} one of B basic orders can be places resulting in the deliverance of corresponding quantity at the beginning of the subsequent period. Additionally, on of U urgent orders can be placed in each period t∈{1,...,T} (with higher costs than the basic order), that is delivered in the same period. If the available quantity exceeds the demand, excess units are stored. Lot-Sizing instances have the naming scheme LotSizing-T-B-U-T.qlp. R is the seed for the random number generator. We provide the following testset:
- T∈{5,6,7,8,9,10}, B∈{3,4} and U∈{2,3}. 50 instances per constellation:
- Download: 1200 QIP instances
Multistage Robust Knapsack Problem
The task is to find a valid knapsack solution for each of T stages with n available items, where uncertainty in the item weights has been added^{2}. The number of items with increased weight is budgeted: in each time step the weight of at most α items can be increased and overall at most β such increases are allowed. The objective ist to maximize the profit resulting from the selected knapsack items but additionally a transition bonus is used to aim for a stable sequence of solutions. Knapsack instances have the naming scheme Knapsack_T-n-R.qlp. R is the seed for the random number generator. We provide the following testset:
- n∈{2,...,7} and T∈{2,...,7}. 50 instances per constellation:
- Download: 1800 QIP instances
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^{1}. 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.
^{1} Further details can be found in this [Ph.D. thesis]
^{2} Further details can be found in this [preprint].