|
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.
|
Downloads
Yasol for Mac OS
Yasol for Linux
Yasol for Windows
Instances
|
