Return to Question

We can model disjunctions (note I am not looking for convex hull) of $t$ unbounded convex polyhedra given by $A^{(1)}x^{(1)}\leq b^{(1)}$,$\dots$,$A^{(t)}x^{(t)}\leq b^{(t)}$ exactly with a mixed integer linear or convex program with $O(t)$ integer variables and perhaps $2^{O(t)}$ real variables?

Let the $i$th convex polyhedra be $A^{(i)}x^{(i)}\leq b^{(i)}$ where $A^{(i)}\in\mathbb R^{m_i\times n}$ and $b^{(i)}\in\mathbb R^{m_i}$ are fixed. Then if we introduce binary variables $y_1,\dots,y_t\in\{0,1\}$ and a real vector $x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$ then $$A^{(i)}x^{(i)}\leq b^{(i)}y_i$$ $$y_1+\dots+y_t=1$$ $$x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$$ suffices.

However the trick breaks down if $b^{(i)}=0$ at $i\in\{1,\dots,t\}$. That is if $b^{(i)}$ are $0$ vectors then the trick breaks down.

If the $t$ polytopes are given by $A^{(i)}x^{(i)}\leq0$ where $A^{(i)}\in\mathbb R^{m_i\times n}$ and $b^{(i)}\in\mathbb R^{m_i}$ are fixed then how do we model unions? Is there a standard trick with at least convex convex constraints introduced?

This is what I am thinking for the case each entry of $x^{(i)}_j\in\mathbb R$ of vectors $x^{(i)}\in\mathbb R^n$ satisfy $0\leq x^{(i)}_j\leq1$. $$B^{(i)}x^{(i)}\leq0$$ $$y_1+\dots+y_t=1$$ $$B^{(i)}=y_iA^{(i)}$$ $$B=B^{(1)}+\dots+B^{(t)}$$ $$x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$$ $$\forall j\in\{1,\dots,j\},z^{(j)}=\sum_{\substack{i=1\\i\neq j}}^tx^{(i)}$$ $$z^{(j)}=AND((1-y_j),x)\mbox{//AND done with linear programming}$$ seems to work if vectors $x^{(i)}$ are non-negative.

By scaling above trick if it works then it also works for case $0\leq x^{(i)}_j\leq\mbox{B}$ for a bound $B$ by scaling $A^{(i)}$.

1. Is my reasoning correct?

2. Is there a general way for arbitrary $x^{(i)}\in\mathbb R^{n}$?

We can model disjunctions (note I am not looking for convex hull) of $t$ unbounded convex polyhedra given by $A^{(1)}x^{(1)}\leq b^{(1)}$,$\dots$,$A^{(t)}x^{(t)}\leq b^{(t)}$ exactly with a mixed integer linear or convex program with $O(t)$ integer variables and perhaps $2^{O(t)}$ real variables?

Let the $i$th convex polyhedra be $A^{(i)}x^{(i)}\leq b^{(i)}$ where $A^{(i)}\in\mathbb R^{m_i\times n}$ and $b^{(i)}\in\mathbb R^{m_i}$ are fixed. Then if we introduce binary variables $y_1,\dots,y_t\in\{0,1\}$ and a real vector $x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$ then $$A^{(i)}x^{(i)}\leq b^{(i)}y_i$$ $$y_1+\dots+y_t=1$$ $$x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$$ suffices.

However the trick breaks down if $b^{(i)}=0$ at $i\in\{1,\dots,t\}$. That is if $b^{(i)}$ are $0$ vectors then the trick breaks down.

If the $t$ polytopes are given by $A^{(i)}x^{(i)}\leq0$ where $A^{(i)}\in\mathbb R^{m_i\times n}$ and $b^{(i)}\in\mathbb R^{m_i}$ are fixed then how do we model unions? Is there a standard trick with at least convex convex constraints introduced?

This is what I am thinking for the case each entry of $x^{(i)}_j\in\mathbb R$ of vectors $x^{(i)}\in\mathbb R^n$ satisfy $0\leq x^{(i)}_j\leq1$. $$B^{(i)}x^{(i)}\leq0$$ $$y_1+\dots+y_t=1$$ $$B^{(i)}=y_iA^{(i)}$$ $$B=B^{(1)}+\dots+B^{(t)}$$ $$x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$$ $$\mbox{//AND done with linear programming}$$ $$//\max(0,a+b-1)\le\mbox{AND}(a,b)\le\min(a,b,1)$$ $$x=\sum_{i=1}^t\mbox{AND}(y_i,x^{(i)})\in\mathbb R^n$$ seems to work if vectors $x^{(i)}$ are non-negative and each entry is in $[0,1]$.

By scaling above trick if it works then it also works for case $0\leq x^{(i)}_j\leq\mbox{B}$ for a bound $B$ by scaling $A^{(i)}$.

1. Is my reasoning correct?

2. Is there a general way for arbitrary $x^{(i)}\in\mathbb R^{n}$?

We can model disjunctions (note I am not looking for convex hull) of $t$ unbounded convex polyhedra given by $A^{(1)}x^{(1)}\leq b^{(1)}$,$\dots$,$A^{(t)}x^{(t)}\leq b^{(t)}$ exactly with a mixed integer linear or convex program with $O(t)$ integer variables and perhaps $2^{O(t)}$ real variables?

Let the $i$th convex polyhedra be $A^{(i)}x^{(i)}\leq b^{(i)}$ where $A^{(i)}\in\mathbb R^{m_i\times n}$ and $b^{(i)}\in\mathbb R^{m_i}$ are fixed. Then if we introduce binary variables $y_1,\dots,y_t\in\{0,1\}$ and a real vector $x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$ then $$A^{(i)}x^{(i)}\leq b^{(i)}y_i$$ $$y_1+\dots+y_t=1$$ $$x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$$ suffices.

However the trick breaks down if $b^{(i)}=0$ at $i\in\{1,\dots,t\}$. That is if $b^{(i)}$ are $0$ vectors then the trick breaks down.

If the $t$ polytopes are given by $A^{(i)}x^{(i)}\leq0$ where $A^{(i)}\in\mathbb R^{m_i\times n}$ and $b^{(i)}\in\mathbb R^{m_i}$ are fixed then how do we model unions? Is there a standard trick with at least convex convex constraints introduced and at least when $x^{(i)}\in[0,1]^n$ holds?

We can model disjunctions (note I am not looking for convex hull) of $t$ unbounded convex polyhedra given by $A^{(1)}x^{(1)}\leq b^{(1)}$,$\dots$,$A^{(t)}x^{(t)}\leq b^{(t)}$ exactly with a mixed integer linear or convex program with $O(t)$ integer variables and perhaps $2^{O(t)}$ real variables?

Let the $i$th convex polyhedra be $A^{(i)}x^{(i)}\leq b^{(i)}$ where $A^{(i)}\in\mathbb R^{m_i\times n}$ and $b^{(i)}\in\mathbb R^{m_i}$ are fixed. Then if we introduce binary variables $y_1,\dots,y_t\in\{0,1\}$ and a real vector $x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$ then $$A^{(i)}x^{(i)}\leq b^{(i)}y_i$$ $$y_1+\dots+y_t=1$$ $$x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$$ suffices.

However the trick breaks down if $b^{(i)}=0$ at $i\in\{1,\dots,t\}$. That is if $b^{(i)}$ are $0$ vectors then the trick breaks down.

If the $t$ polytopes are given by $A^{(i)}x^{(i)}\leq0$ where $A^{(i)}\in\mathbb R^{m_i\times n}$ and $b^{(i)}\in\mathbb R^{m_i}$ are fixed then how do we model unions? Is there a standard trick with at least convex convex constraints introduced?

This is what I am thinking for the case each entry of $x^{(i)}_j\in\mathbb R$ of vectors $x^{(i)}\in\mathbb R^n$ satisfy $0\leq x^{(i)}_j\leq1$. $$B^{(i)}x^{(i)}\leq0$$ $$y_1+\dots+y_t=1$$ $$B^{(i)}=y_iA^{(i)}$$ $$B=B^{(1)}+\dots+B^{(t)}$$ $$x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$$ $$\forall j\in\{1,\dots,j\},z^{(j)}=\sum_{\substack{i=1\\i\neq j}}^tx^{(i)}$$ $$z^{(j)}=AND((1-y_j),x)\mbox{//AND done with linear programming}$$ seems to work if vectors $x^{(i)}$ are non-negative.

By scaling above trick if it works then it also works for case $0\leq x^{(i)}_j\leq\mbox{B}$ for a bound $B$ by scaling $A^{(i)}$.

1. Is my reasoning correct?

2. Is there a general way for arbitrary $x^{(i)}\in\mathbb R^{n}$?

We can model disjunctions (note I am not looking for convex hull) of $t$ unbounded convex polyhedra given by $A^{(1)}x^{(1)}\leq b^{(1)}$,$\dots$,$A^{(t)}x^{(t)}\leq b^{(t)}$ exactly with a mixed integer linear or convex program with $O(t)$ integer variables and perhaps $2^{O(t)}$ real variables?

Let the $i$th convex polyhedra be $A^{(i)}x^{(i)}\leq b^{(i)}$ where $A^{(i)}\in\mathbb R^{m_i\times n}$ and $b^{(i)}\in\mathbb R^{m_i}$ are fixed. Then if we introduce binary variables $y_1,\dots,y_t\in\{0,1\}$ and a real vector $x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$ then $$A^{(i)}x^{(i)}\leq b^{(i)}y_i$$ $$y_1+\dots+y_t=1$$ $$x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$$ suffices.

However the trick breaks down if $y_i=0$ at $i\in\{1,\dots,t\}$. That is if $y_i$ are $0$ vectors then the trick breaks down.

If the $t$ polytopes are given by $A^{(i)}x^{(i)}\leq0$ where $A^{(i)}\in\mathbb R^{m_i\times n}$ and $b^{(i)}\in\mathbb R^{m_i}$ are fixed then how do we model unions? Is there a standard trick with at least convex convex constraints introduced?

We can model disjunctions (note I am not looking for convex hull) of $t$ unbounded convex polyhedra given by $A^{(1)}x^{(1)}\leq b^{(1)}$,$\dots$,$A^{(t)}x^{(t)}\leq b^{(t)}$ exactly with a mixed integer linear or convex program with $O(t)$ integer variables and perhaps $2^{O(t)}$ real variables?

Let the $i$th convex polyhedra be $A^{(i)}x^{(i)}\leq b^{(i)}$ where $A^{(i)}\in\mathbb R^{m_i\times n}$ and $b^{(i)}\in\mathbb R^{m_i}$ are fixed. Then if we introduce binary variables $y_1,\dots,y_t\in\{0,1\}$ and a real vector $x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$ then $$A^{(i)}x^{(i)}\leq b^{(i)}y_i$$ $$y_1+\dots+y_t=1$$ $$x=\sum_{i=1}^tx^{(i)}\in\mathbb R^n$$ suffices.

However the trick breaks down if $b^{(i)}=0$ at $i\in\{1,\dots,t\}$. That is if $b^{(i)}$ are $0$ vectors then the trick breaks down.

If the $t$ polytopes are given by $A^{(i)}x^{(i)}\leq0$ where $A^{(i)}\in\mathbb R^{m_i\times n}$ and $b^{(i)}\in\mathbb R^{m_i}$ are fixed then how do we model unions? Is there a standard trick with at least convex convex constraints introduced and at least when $x^{(i)}\in[0,1]^n$ holds?