Quantified (Mixed) Integer Linear 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. This is the point where Q-MIPs are intended to support future modeling.

In 2007, Subramani coined the terms Quantified Linear Program and Quantified Integer Program and thus extended the traditional notions of Linear and Integer Programming [1]. The resulting quantified programs are both a strong modelling language and an intuitive input to next generation optimization software.

We extended this notion one step further and introduced a minimax objective [2]:

... as well as a restricted mixed version with the following attributes:

• the objective is minmax (more exactly: min max min … max min max) and is linear for any single game
• integer variables are allowed on all exist-stages
• (only) binary variables are allowed on universal stages
• continuous variables are allowed (only) on the last stage, assuming it is an existential stage
• quantifiers are either existential or universal

[1] K. Subramani: On a decision procedure for quantified linear programs. Ann. Math. Artif. Intell. 51(1): 55-77 (2007)
[2] U. Lorenz, J. Wolf: Solving Multistage Quantified Linear Optimization Problems with the Alph-beta nested Benders Decomposition, EURO Journal on Computational Optimization, pp. 349 - 370, Springer 2015

Downloads

Yasol for Mac OS
Yasol for Linux
Yasol for Windows
Instances

About

Yasol
QMIPs