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. 

QIP test instances


Multistage Robust Selection Problem

The task is to select p out of n=2p items, such that the costs are minimized1 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:


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 costs1 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:


Multistage Robust Lot-Sizing Problem

We consider a single item lot-sizing problem with discrete ordering decisions and T periods2. At the beginning of each time period, the product demand that needs to be satisfied is disclosed: Either dt or dt. 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:

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 added2. 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:

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 airplanes1. 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:


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. 

Instance collection IP based

Instance collection MIP based

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].

527efb333