Quantified mixed-integer programming

Researchgroup TOR, Quelle: http://commons.wikimedia.org/wiki/File:Mathematics_concept_collage.jpg

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

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
END

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

  1. 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.
  2. 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.
  3. 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.