A tiny Q-MIP

Let x1 and x3 be existential variables and x2 a universal variable. Thus we have, ∃x1 ∀x2 ∃x3. The aim is to find an optimal first stage setting for x1 such that the objective max_x1( x1 + min_x2 ( x2 + max_x3 ( x3 ) ) ) is optimized, and such that

-2x2 -1x3 ≤ -2
-1x1 +2x2 +1x3 ≤ 2
2x1 + 4x2 ≤ 6

0 ≤ x1 ≤ 2
0 ≤ x2 ≤ 1
0 ≤ x3 ≤ 2

Let x1 be integer, x2 binary, and x3 be continuous.

Then the objective value is 3 and the optimal assignment of x1 is 1. Moreover, x3 should be set to either 0 or 2, depending on whether x2 becomes 1 or 0. It is possible to visualize the policy. In the following picture, you see an outer 3d-polytope which is caught in a box. That is the polytope which is generated by the existential LP-relaxation, i.e. all variables are assumed to be existential and continuous. Within the given polytope you see another one, in light red. That is the union of all 3D-points that are part of any feasible policy of the existential player, given the original ∃∀∃ quantifier string. You can also see that x1 can be set between 0 and 1 (i.e. half of the box in x1 -direction) and depending on how x2 is set (either 0 or 1), x3 can be moved up to its upper bound 2 or must smaller or equal to 1.

You can download the QLP file for this instance. For a closer look at the file format see this page.


Yasol for Mac OS
Yasol for Linux
Yasol for Windows