Equivalence between a PORTA output and Polymake output for same input

[Tryer]

Hello,

In PORTA, I process the test.poi file with content reproduced below (the online message system does not allow me to attach a .poi file):

Code: Select all

DIM = 6 CONV_SECTION 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 CONE_SECTION 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 END

On running this through PORTA, to generate the facets, I obtain the file test.poi.ieq, contents of which are reproduced below:

Code: Select all

DIM = 6 VALID 0 0 0 1 1 1 INEQUALITIES_SECTION ( 1) -x1 -x6 <= -1 ( 2) -x2 -x4 <= -1 ( 3) -x3-x4 <= -1 ( 4) -x3 -x5 <= -1 ( 5) -x4 -x6 <= -1 ( 6) -x5-x6 <= -1 ( 7) -x1 <= 0 ( 8) -x2 <= 0 ( 9) -x3 <= 0 ( 10) -x4 <= 0 ( 11) -x5 <= 0 ( 12) -x6 <= 0 END

I am attempting to reproduce the same output via Polymake by creating attached file points.txt reproduced below:

Code: Select all

1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1

Essentially, I have mapped the points in the porta input in CONV_SECTION contents to the first 8 rows of the polymake input file by prepending a 1 to denote that it is a point. The 6 rays of CONE_SECTION, I have mapped as the last 6 rows of the polymake input file by preprending a 0 to denote that it should be interpreted as a ray. I have done so based on the discussion in this thread in the forum: viewtopic.php?f=8&t=24

When I have polymake read this input file and print the facets, I obtain the following:

Code: Select all

Facets: 0: x1 >= 0 1: x5 >= 0 2: x4 >= 0 3: 0 >= -1 4: x6 >= 0 5: x4 + x6 >= 1 6: x5 + x6 >= 1 7: x1 + x6 >= 1 8: x2 >= 0 9: x3 >= 0 10: x3 + x4 >= 1 11: x2 + x4 >= 1 12: x3 + x5 >= 1

I am having a tough time interpreting Facet # 3 which says 0 >= -1. Why does polymake provide this as a facet? I have been able to confirm that all of the other facets generated by polymake indeed match the facets given by PORTA.

Can one safely disregard a facet generated by polymake which does not have any variable in it?

Thanks.

[joswig]

If "0 >= -1" occurs as a facet, then your polyhedron is necessarily unbounded. The converse, by the way, is not true.

The thing is that combinatorially polymake treats all polyhedra as bounded polytopes (with a marked face at infinity, which may have any dimension). This has a number of algorithmic advantages.

It works as follows: Modulo its lineality space any polyhedron is pointed (i.e., it has at least one vertex). Such a polyhedron is projectively equivalent to a polytope. See Section 3.6.3 of Polyhedral and Algebraic Methods in Computational Geometry.

While this inequality seems to be irrelevant it does matter for the combinatorics. polymake keeps, e.g., the FACETS and the rows of VERTICES_IN_FACETS in sync. This way a facet index is globally valid, in all properties of the Polytope object. Therefore it needs to stay there. For most subsequent computations you can ignore it, of course.

Here is an easy example. The polyhedron is the positive orthant in R^2. Combinatorially, it is a triangle (with a marked edge/facet).

Code: Select all

polytope > $P = new Polytope(INEQUALITIES=>[[0,1,0],[0,0,1]]); polytope > print $P->FACETS; 0 1 0 0 0 1 1 0 0

You can see the marked face as follows:

Code: Select all

polytope > print $P->FAR_FACE; {0 1}

Those indices refer to the numbering of the VERTICES:

Code: Select all

polytope > print rows_numbered($P->VERTICES); 0:0 1 0 1:0 0 1 2:1 0 0

So the guys with indices 0 and 1 are rays (which you can also detect from the leading zeros in the coordinate representation).