2
$\begingroup$

Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows:

$P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ for $j=1\dots,r$.

Is it possible to derive the H-representation of the convex hull of the union of $P_j$s, i.e., ConvexHull$(\bigcup_j P_j)$, efficiently?

$\endgroup$

1 Answer 1

3
$\begingroup$

If you're okay with additional variables, then the answer is yes. This follows from Balas's extended formulation for the disjunction of polyhedra. It shows that $\operatorname{convex}.\operatorname{hull} ( \cup_j P_j)$ admits an extended formulation of size at most $\sum_{j}(\operatorname{xc}(P_j)+1)$, where $\operatorname{xc}(\cdot)$ denotes extension complexity. (The extension complexity of $P_j$ is at most the number of inequalities defining $P_j$.)

I have not thought about whether this can be done in the original space of variables.

$\endgroup$
2
  • $\begingroup$ @ Austin: Now this question arises: If the extended formulation of convex hulls for two sets of polytopes are equivalent, can it be the case that the original convex hulls are also equivalent? $\endgroup$
    – Star
    Aug 5, 2015 at 15:36
  • $\begingroup$ @how many variables do you need? $\endgroup$
    – Turbo
    Aug 13, 2019 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.