# Quantified mathematical programming

Mixed-integer linear programming (MIP) is a well-established state-of-the-art technique for computer-aided optimization. However, companies observe an increasing danger of disruptions that prevent them from acting as planned. One reason is that input data is often assumed to be deterministic, but in reality, they are afflicted with uncertainties which cannot be adequately described in MIPs, often. To overcome this drawback, Subramani extended the MIP-formulation by the introduction of quantifiers [1]. The resulting quantified programs are both a strong modelling language and an intuitive input to next generation optimization software. Currently, we investigate the purely continuous variant (QLP) and the purely integer variant (QIP).

## A small QLP instance

In the table below you find test instances collections and numerical data.

Test instances, description | Download | Results |
---|---|---|

A collection of 797 QSAT instances in QLP/QIP-format | Download | |

A collection of artificial QIP (0/1) instances, created with the help of the MIP2003 testset. | ||

Quantified carsequencing | ||

Quantified jobshop | ||

Booster station design |

# The QLP File Format

As an input for QMIP optimization software, a new standardized file format is required. We extended the CPLEX-LP file format to handle quantifiers.The so called QLP file format is based on the CPLEX-LP file format. Some mandantory modifications have to be considered. A typical QLP file (belonging to the above example) looks as follows:MINIMZE

– x1 – 2 x2 – 2 x3

SUBJECT TO

– x2 – x3 <= -1

– x1 + x2 + x3 <= 1

2 x1 + 2 x2 <= 3

BOUNDS

0 <= x1 <= 2

0 <= x2 <= 2

0 <= x3 <= 2

GENERALS

x3

EXISTS

x1 x3

ALL

x2

ORDER

x1 x2 x3

ENDThe differences between the CPLEX-LP file format and the QLP file format are as follows:

MAXIMIZE / MINIMIZE

SUBJECT TO

BOUNDS

INFINITY

FREE

GENERALS

BINARIES

ALL*

EXISTS*

RANDOM*

ORDER*

END

New keywords are marked with *. Every keyword has to be written in capital letters. Abbreviations are not allowed.

As an input for QMIP optimization software, a new standardized file format is required. We extended the CPLEX-LP file format to handle quantifiers.

The so called QLP file format is based on the CPLEX-LP file format. Some mandantory modifications have to be considered. A typical QLP file (belonging to the above example) looks as follows:

MINIMZE

– x1 – 2 x2 – 2 x3

SUBJECT TO

– x2 – x3 <= -1

– x1 + x2 + x3 <= 1

2 x1 + 2 x2 <= 3

BOUNDS

0 <= x1 <= 2

0 <= x2 <= 2

0 <= x3 <= 2

GENERALS

x3

EXISTS

x1 x3

ALL

x2

ORDER

x1 x2 x3

END

The differences between the CPLEX-LP file format and the QLP file format are as follows:

- The keywords are

MAXIMIZE / MINIMIZE

SUBJECT TO

BOUNDS

INFINITY

FREE

GENERALS

BINARIES

ALL*

EXISTS*

RANDOM*

ORDER*

END

New keywords are marked with *. Every keyword has to be written in capital letters. Abbreviations are not allowed. - The BOUNDS section which follows the constraint section is mandatory. Each bound definition has to begin on a new line. The general form is l≤x≤u.
- The BOUNDS section is followed by typifying the variables. To specify any of the variables as general integer variables, a GENERAL section has to be added; to specify any of the variables as binary integer variables, a BINARY section has to be added. In every section the variables are separated by at least one space. Moreover, every variable is marked with one of the new keywords ALL, EXISTS or RANDOM. Analogously the variables in the ALL, EXISTS and RANDOM section are separated by at least one space. In case the order of the quantification differs from the order of the variables of the objective function, the block ORDER can be used.

[1] K. Subramani: On a decision procedure for quantified linear programs. Ann. Math. Artif. Intell. 51(1): 55-77 (2007)