Equivalence between a PORTA output and Polymake output for same input

Questions and problems about using polymake go here.
Tryer
Posts: 13
Joined: 28 Feb 2022, 17:53

Equivalence between a PORTA output and Polymake output for same input

Postby Tryer » 04 Mar 2022, 16:47

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.
Attachments
points.txt
(196 Bytes) Downloaded 26 times

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

Re: Equivalence between a PORTA output and Polymake output for same input

Postby joswig » 04 Mar 2022, 17:36

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).


Return to “Helpdesk”