## A tiny Q-MIP

Let x_{1} and x_{3} be existential variables and x_{2} a universal variable. Thus we have, ∃x_{1} ∀x_{2} ∃x_{3}. The aim is to find an optimal first stage setting for x_{1} such that the objective max_x_{1}( x_{1} + min_x_{2}( x_{2} + max_x_{3} ( x_{3} ) ) ) is optimized, and such that

-2x_{2} -1x_{3} ≤ -2

-1x_{1} +2x_{2} +1x_{3} ≤ 2

2x_{1} + 4x_{2 }≤ 6

0 ≤ x_{1} ≤ 2

0 ≤ x_{2} ≤ 1

0 ≤ x_{3} ≤ 2

Let x_{1} be integer, x_{2} binary, and x_{3} be continuous.

Then the objective value is 3 and the optimal assignment of x_{1} is 1. Moreover, x_{3} should be set to either 0 or 2, depending on whether x_{2} 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 x_{1} can be set between 0 and 1 (i.e. half of the box in x1-direction) and depending on how x_{2} is set (either 0 or 1), x_{3} 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.