Defining not pointed polyhedra via POINTS

[Etsche]

Hello,

I'm trying to compute the minimal faces of a polyhedron P, given through inequalities. The problem seems to be, that the polyhedron is not necessarily pointed. E.g. I tried computing the minimal faces as the Minkowski-sum of a bounded vertex and the lineality space. While doing so I discovered two problems:

1) Defining a not pointed polyhedron via POINTS leads to a polyhedron, which has no lineality space, i.e. is pointed (in this example the polyhedron is a cone, of which I thought polymake 2.10 can handle now):

Code: Select all

polytope > $P = new Polytope<Rational>(POINTS=>[[1,0,0],[0,1,1],[0,-1,-1]]); polytope > print $P->LINEALITY_DIM; 0

2) The Minkowski-sum of two polyhedra is not, what I would expect it to be. E.g. for every polyhedron P I would expect: P + {0} = P:

Code: Select all

polytope > $P = new Polytope<Rational>(INEQUALITIES=>[[0,1,0,0]]); polytope > $Z = new Polytope<Rational>(POINTS=>[[1,0,0,0]]); polytope > $M = minkowski_sum($P,$Z); polytope > print $M->DIM; 1

Again, polyhedra with a trivial lineality space work just fine.
I am mostly interested in getting the minimal faces, so any other way I might have overlooked would be as welcome as help regarding the two problems described.

[paffenholz]

Unfortunately you have found two bugs in one blow.

The first is already during initialization. If the input does not explicitely contain some section defining lineality then the polytope is assumed to be pointed. As a workaround you could state (part of the) lineality space in the input:

Code: Select all

$P=new Polytope(POINTS=>[[1,0,0],[0,1,1],[0,-1,-1]], INPUT_LINEALITY=>[[0,1,1]]);

The only important thing here is that the section INPUT_LINEALITY is present and not empty. It need not be the full lineality space, POINTS can contain further generators for it.

Actually the computation of FACETS and AFFINE_HULL still works, so if you don't know any vector in the lineality space you could do

Code: Select all

$P = new Polytope<Rational>(POINTS=>[[1,0,0],[0,1,1],[0,-1,-1]]); $Q:=new Polytope(INEQUALITIES=>$P->FACETS, EQUATIONS=>$P->AFFINE_HULL);

and work with $Q.

The problem with the second is that the minkowski_sum function currently only works for pointed polyhedra but doesn't check this. As a workaround you can add back the lineality space afterwards via

Code: Select all

$Q=new Polytope(POINTS=>$M->POINTS, INPUT_LINEALITY=>$P->LINEALITY_SPACE/$Z->LINEALITY_SPACE);

I'm sorry for this inconvenience.

[Etsche]

Thanks a lot for the workaround! Just what I was looking for.

[joswig]

The first is already during initialization. If the input does not explicitely contain some section defining lineality then the polytope is assumed to be pointed. As a workaround you could state (part of the) lineality space in the input:

Code: Select all

$P=new Polytope(POINTS=>[[1,0,0],[0,1,1],[0,-1,-1]], INPUT_LINEALITY=>[[0,1,1]]);

The only important thing here is that the section INPUT_LINEALITY is present and not empty. It need not be the full lineality space, POINTS can contain further generators for it.

Actually, for several reasons this solution is not as good. Please apply the attached patch by

Code: Select all

patch -p0 < initial.patch

at the polymake root directory (the one containing the apps directory). Works on installed version, does not need recompilation.

This fixes only the first of the two bugs reported. The other (concerning the Minkowski sums) is considered less critical. It will be fixed in the next release. For now Andreas' workaround should work out fine.

[Etsche]

Unfortunately the patch is not working for me. Applying seemed to be successfull but the first example I posted has not changed. P is still pointed.

[joswig]

Unfortunately the patch is not working for me. Applying seemed to be successfull but the first example I posted has not changed. P is still pointed.

This is my output on your example with the patch:

Code: Select all

polytope > $P = new Polytope<Rational>(POINTS=>[[1,0,0],[0,1,1],[0,-1,-1]]); polytope > print $P->LINEALITY_DIM; 1

Are you sure you applied the patch to the file apps/polytope/rules/initial.rules in the installed version of polymake? Please do the following:

Code: Select all

polytope > $P = new Polytope<Rational>(POINTS=>[[1,0,0],[0,1,1],[0,-1,-1]]); polytope > save ($P,"my.poly");

Please post that file my.poly together with your apps/polytope/rules/initial.rules.

[Etsche]

Thanks for the answer. Indeed, I did not install the patch in the correct polymake-folder. I patched an old version on my system, so it could not work.

Nevertheless applying the patch in the correct directory did not work, too. Trying to launch polymake produced the error:

Code: Select all

Welcome to polymake version 2.10, released on June 20, 2011 Copyright (c) 1997-2011 Ewgenij Gawrilow, Michael Joswig (TU Darmstadt) http://www.polymake.org This is free software licensed under GPL; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Loading applications now...polymake: ERROR: "/usr/local/share/polymake/apps/polytope/rules/initial.rules", line 23: Invalid separator character '(' in attribute list near "sub __prec__aaa248 : method " "/usr/local/share/polymake/apps/polytope/rules/initial.rules", line 29: Invalid separator character '(' in attribute list near "sub __prec__aaa250 : method "

So I looked in the file initial.rules and changed the code to:

Code: Select all

object Polytope { rule initial : FEASIBLE : INEQUALITIES | EQUATIONS { $this->FEASIBLE = cdd_input_feasible($this); } rule initial : FEASIBLE : POINTS | VERTICES { $this->FEASIBLE = ($this->POINTS | VERTICES)->rows; } }

This is something in between the old and the patched version. It fixed the startup error and not-pointed polyhedra now have a lineality space. Is this approach ok?

[gawrilow]

The parser for rulefiles has changed since the released version 2.10, so that the presented patch probably does not fit your code base. You would be on a safer side if you apply it to the current SVN snapshot, but if your solution works fine for you, you can surely leave it as is.

[joswig]

Is this approach ok?

Yes, this is OK. Sorry for the inconvenience. I did not pay attention to the change Ewgenij mentioned above. My bad.