On disjunction convex hulls for generalized cross polytopes

Abstract

We continue the study of the natural polytope $\mathcal{D}$ in ${\mathbb{R}}^{n+d}$ associated with the disjunction of a set of $n+1$ polytopes in ${\mathbb{R}}^d$, managed by $n$ binary variables. Already $\mathcal{D}$ had been characterized for arbitrary $n\ge 1$ and (i) $d\in \{1,2\}$, and (ii) for a broad generalization of hyper-rectangles. In both cases, the complete characterization employs full optimal big-M lifting. Here, we give a complete description of $\mathcal{D}$ for the case of $n=1$ and arbitrary $d$, when the (two) polytopes are arbitrary generalized cross polytopes. Furthermore, we characterize when our complete description employs only optimal big-M lifting. For $n>1$, we generalize the family of facet-describing inequalities used for $n=1$. Finally, we carry out some computational experiments demonstrating the value of our theoretical results.