Quantified Mathematical Programming

Mixed-integer linear programming (MIP) is a well-established state-of-the-art technique for computer-aided optimization. Especially, in order to support the planning for logistics, this form of mathematical optimization has become standard. 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 usually cannot be adequately described in MIPs. Currently, there are several activites which try to overcome this drawback. One of them is called

Quantified (Mixed Integer) Linear Programming

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. They serve with a rigorous formalism that allows to incorporate uncertainty bits into traditional MIP forlmulations. We mainly investigate the pure continuous variant (QLP), the pure integer variant (QIP), and a mixed variant where variables of the last stage may be continuous or discrete but the variables of all other stages have to be binary. We extended the original definition by an objective function.

QLPDef

A small QLP instance is the following.

max ( 3x₁ + min ( x₂ + max x₃ )))
x₁ x₂ x₃

such that

[1] K. Subramani. An Analysis of Quantified Linear Programs, Proc. of Discrete Mathematics and Theoretical Computer Science, LNCS Vol 2731, Springer, 2003, http://dx.doi.org/10.1007/3-540-45066-1_21

[2] J. Wolf. Quantified Linear Programming, Dissertation, 2014 to appear

[3] T. Ederer, U. Lorenz, T. Opfer. Quantified Combinatorial Optimization, Proc. OR 2013, pp. 121 - 128, Springer, 2014 (slides)

[4] U. Lorenz. Multistage Optimization with the help of Quantified Linear Programming, Talk on OR 2014 (slides)

Benchmarking

... to appear

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:

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.

Aktualisiert via XIMS am 24.11.2014 von U. Lorenz