On disjunction convex hulls for generalized cross polytopes

Summary · qwen2.5:32b

The study provides a complete characterization of the disjunction convex hull $\mathcal{D}$ in $\mathbb{R}^{n+d}$ for generalized cross polytopes when $n=1$ and any $d$, using optimal big-M lifting techniques; it also extends facet-describing inequalities to cases where $n>1$. This work matters as it advances the theoretical understanding of convex hulls associated with disjunctions, which is crucial for optimization problems involving binary variables. A concrete detail is that computational experiments were conducted to validate the theoretical findings.

Suggested post angle

Exploring disjunction convex hulls for generalized cross polytopes in real-time rendering.

Excerpt

arXiv:2607.03460v1 Announce Type: new 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\geq 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.