Corollary 13.21 — lifted description of $\mathrm{conv}(P(r_1)\cup P(r_2))$ via $\mathrm{conv}\,Z(r_1,r_2)$

This is Corollary 13.21 of Balas's Disjunctive Programming: the same-ground-set specialization of Proposition 13.16, obtained through the same-space reduction of Theorem 13.18.

Let $r_1,r_2$ be set functions on $N=\{1,\dots,n\}$ satisfying conditions 1-3 of Application 1: $r(\emptyset)=0$, $r(A)\le|A|$ for $A\subsetneq N$, and $r$ nondecreasing. Let $P(r_i) := \{x\in[0,1]^n : x(A)\le r_i(A)\ \forall A\subseteq N\}$ be the corresponding polytopes in the unit cube. Then $\mathrm{conv}(P(r_1)\cup P(r_2))$ is the set of $w\in[0,1]^n$ for which there exist $x,y\in[0,1]^n$ with

and

By Proposition 13.16 the last two conditions say exactly that $(x,y)\in\mathrm{conv}\,Z(r_1,r_2)$. In the complemented variables $\bar w = \mathbf 1-w$, $\bar x=\mathbf 1-x$, $\bar y=\mathbf 1-y$, where the polytopes become upper monotone and Theorem 13.18 applies, the relation reads $\bar w=\bar x+\bar y$.

Formalization Note. The retired version wrote $w = x + y$ in the original variables and put no box constraints on $x, y$. Then for $r_1=r_2\equiv0$ it admitted $w=1$ although $\mathrm{conv}(P(r_1)\cup P(r_2))=\{0\}$. The polymatroid-type polytopes $P(r_i)$ are lower monotone, while Theorem 13.18 is stated for upper monotone polytopes, so the reduction must be applied in complemented variables. Translated back, this gives $w = x+y-\mathbf 1$ with $(x,y)\in\mathrm{conv}\,Z\subseteq[0,1]^{2n}$; the box constraints of Proposition 13.16 are now explicit. As in Application 1, the polytopes are taken inside $[0,1]^n$, i.e. $P(r_i)\cap[0,1]^n$. For $n\ge2$ this is automatic from $r(\{j\})\le1$, and for $n=1$ it is the reading under which the right-hand side, a subset of $[0,1]^n$, can match.