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 20 Aug '15, 22:34

frogeyedpeas's gravatar image

frogeyedpeas
154
accept rate: 0%

edited 20 Aug '15, 22:35


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.

link

answered 21 Aug '15, 11:17

rschwarz's gravatar image

rschwarz
366210
accept rate: 21%

edited 21 Aug '15, 11:17

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×21
×20
×8
×5

Asked: 20 Aug '15, 22:34

Seen: 1,000 times

Last updated: 21 Aug '15, 11:17

OR-Exchange! Your site for questions, answers, and announcements about operations research.