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$
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 '15 at 15:36
  • $\begingroup$ @how many variables do you need? $\endgroup$ – 1.. Aug 13 '19 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.