Trivial 0 >= -1 inequality among the facets

Questions and problems about using polymake go here.
athos
Posts: 3
Joined: 07 Feb 2013, 14:48

Trivial 0 >= -1 inequality among the facets

Postby athos » 07 Feb 2013, 14:53

Hi!

I am new to polymake. I define a polyhedron, and the inequality
0 >= -1
is among the facets. Thus the number of facets returned is false. Is this a bug or a feature?

Attila

Details:

$points=new Matrix<Rational>([
[1,1,1,1,1,0,0,0,0],
[1,1,0,0,0,0,0,0,1],
[1,0,1,0,0,1,0,0,0],
[1,0,0,1,0,0,1,0,0],
[1,0,0,0,1,0,0,1,0],
[1,0,0,0,0,1,1,0,0],
[1,0,0,0,0,1,0,1,0],
[1,0,0,0,0,1,0,0,1],
[1,0,0,0,0,0,1,1,0],
[1,0,0,0,0,0,1,0,1],
[1,0,0,0,0,0,0,1,1],
[0,1,0,0,0,0,0,0,0],
[0,0,1,0,0,0,0,0,0],
[0,0,0,1,0,0,0,0,0],
[0,0,0,0,1,0,0,0,0],
[0,0,0,0,0,1,0,0,0],
[0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,0],
[0,0,0,0,0,0,0,0,1]]);

$p=new Polytope<Rational>(POINTS=>$points);

print_constraints($p);

User avatar
assarf
Developer
Posts: 74
Joined: 12 Oct 2011, 15:52

Re: Trivial 0 >= -1 inequality among the facets

Postby assarf » 07 Feb 2013, 16:05

Hi there,

it is a feature. The inequality 0>=-1 describes the "far-facet", which is the facet at infinity. So this inequality only belongs to a facet, if your polyhedron is unbounded. In a bounded polyhedron this should indeed never appear as a facet.

Your polyhedron -- the way you entered it -- is unbounded with quite many rays. So I am guessing that your input is not correct. Especially because of this part here:

Code: Select all

[0,1,0,0,0,0,0,0,0], [0,0,1,0,0,0,0,0,0], [0,0,0,1,0,0,0,0,0], [0,0,0,0,1,0,0,0,0], [0,0,0,0,0,1,0,0,0], [0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,0], [0,0,0,0,0,0,0,0,1]
Keep in mind, that polymake uses homogeneous coordinates. Check: http://www.polymake.org/doku.php/tutorial/coordinates or wikipedia for more information (if you don't know about homogeneous coordinates, you should read that).

BUT, to give a very simplified explanation:
Points always need to have a 1 as a first coordinate. And rays have a 0 as the first coordinate.

So this means that polymake interprets your input as follows:
A polytope which has the following points ("normal" coordinates):

Code: Select all

(1,1,1,1,0,0,0,0) (1,0,0,0,0,0,0,1) (0,1,0,0,1,0,0,0) (0,0,1,0,0,1,0,0) (0,0,0,1,0,0,1,0) (0,0,0,0,1,1,0,0) (0,0,0,0,1,0,1,0) (0,0,0,0,1,0,0,1) (0,0,0,0,0,1,1,0) (0,0,0,0,0,1,0,1) (0,0,0,0,0,0,1,1)
And with rays in the following direction:

Code: Select all

(1,0,0,0,0,0,0,0) (0,1,0,0,0,0,0,0) (0,0,1,0,0,0,0,0) (0,0,0,1,0,0,0,0) (0,0,0,0,1,0,0,0) (0,0,0,0,0,1,0,0) (0,0,0,0,0,0,1,0) (0,0,0,0,0,0,0,1)
Which is the complete Space R^8. I guess this is not what you wanted. So just add a new coordinate at the beginning of each point and set it to 1. Now you should be good to go.

Greetings
no signature

athos
Posts: 3
Joined: 07 Feb 2013, 14:48

Re: Trivial 0 >= -1 inequality among the facets

Postby athos » 08 Feb 2013, 17:02

Dear Assarf,

Thank you for your reply.
The polyhedron was what I wanted: I wanted the uphull (or dominant) of certain points (instead of their convex hull). And I was happy with the output, so I think this is what I wanted.

I will try to understand whether this what you write about the trivial inequality is an unavoidable corollary of using homogeneous coordinates. But what you write means that the returned number of facets
print $p->N_FACETS;
is only correct if $p is bounded. (Of course I can live with that.)



Attila

User avatar
joswig
Main Author
Posts: 280
Joined: 24 Dec 2010, 11:10

Re: Trivial 0 >= -1 inequality among the facets

Postby joswig » 09 Feb 2013, 10:01

But what you write means that the returned number of facets
print $p->N_FACETS;
is only correct if $p is bounded. (Of course I can live with that.)
polymake's polytope semantics describes a projectively equivalent (bounded) polytope for every possibly unbounded polyhedron. Not every unbounded polyhedron has the far hyperplane as a facet. Notice also that if your polyhedron has a non-trivial lineality space this is factored out, too, for the combinatorics.


Return to “Helpdesk”