Suppose I have two polyhedrons given as $$ A_1 x \le b_1 $$ And $$ A_2 x \le b_2 $$ Whereas ( A_1, A_2) are real matrices, (x \in \Bbb{R}^n ) and ( b_1,b_2 ) have the vertical dimension as(A_1,A_2 ) respectively. The question is how do I generate the matrix and vector ( A_3, b_3 ) such that $$ A_3 x \le b_3 $$ Is the minimal convex hull containing the two aforementioned polyhedrons?
asked
frogeyedpeas |

There is an extended formulation for the convex hull of the union of (bounded) polytopes. You can look at the paper "Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems" by Egon Balas (1984). But it is actually straightforward: You create copies \(x_1, x_2\) of your variables \(x\) for each polytope and add the equation \( x = x_1 + x_2 \). You also add variables \(y_1, y_2 \in [0, 1]\) with \( y_1 + y_2 = 1 \). Then you restrict your copies of variables: \( A_1 x_1 \le b_1 y_1, \quad A_2 x_2 \le b_2 y_2 \). The \(x\) are now in effect a convex combination of points that live in the respective polytopes. There is also a version for unbounded polyhedra, but it will you give to the (topological) closure of the union, which might be open. If you don't want to add extra variables, you can try to eliminate them by Fourier-Motzkin. This has worked very well for me, when the dimension of \(x\) is small.
answered
rschwarz |