Page 1 of 1

Error when using projection command

Posted: 02 Feb 2018, 00:31
by soheilmn
Hi,
I am trying to perform a "projection" operation on a polytope with 9 0-1 variables and 9 nonnegative continuous variables. This is the set of qualities and inequalities that form the feasible region of a well-known mixed-integer program, which is attached to this message.

To obtain the facets, I run the following commands in polymake:

Code: Select all

$m = lp2poly('/Users/test/Documents/Research/SFCNF/PolyMake/fcnf.lp'); $p = new Polytope<Rational>($m); print $p->N_LATTICE_POINTS; $q = projection($p, [1, 2, 3, 4, 5, 6, 7, 8, 9]);
The first three lines are executed flawlessly, but polymake seems to get stuck with the fourth command; when I run the command, polymake runs for a few minutes and then suddenly it prints the following output, which seems polymake has crashed. Is this because this is probably a large-scale problem for polymake or I am missing something here?
/Applications/polymake.app/Contents/MacOS/polymake.start: line 66: 70837 Killed: 9 $ResourcesDir/polymake/bin/polymake
logout
Saving session...
...copying shared history...
...saving history...truncating history files...
...completed.

[Process completed]
I am using polymake 3.1 on iOS 10.13.1. Thank you very much for your help.

Re: Error when using projection command

Posted: 02 Feb 2018, 09:45
by gawrilow
In fact, the projection function tries to allocate bizarre amounts of memory. Continue investigations with a debug build, maybe there is some negative number misinterpreted as an array size or such...

Re: Error when using projection command

Posted: 02 Feb 2018, 10:12
by joswig
Please recall that projecting a polytope down by one dimension might (asymptotically) square the number of facets. Loosing nine dimension this might result in an enormous number of facets. As a side comment: exploiting the reverse is the idea behind the so-called "extended formulations"; see, e.g., https://arxiv.org/abs/1107.0371. So it is perfectly normal that polymake may require a lot of memory.

In your case I recommend the following:

Code: Select all

> $p=lp2poly("fcnf.lp"); > $p->VERTICES; > q = projection($p, [1, 2, 3, 4, 5, 6, 7, 8, 9],nofm=>1);
The second command triggers the dual convex hull computation which is pretty simple in this case. The projection with the option "nofm=>1" avoids computing the facets (via iterated projections, i.e., Fourier-Motzkin elimination). Again this becomes a simple computation which will, e.g. allows you to find out (without knowing the facets yet):

Code: Select all

> print $q->N_VERTICES; 936
Yet, finding the facets of the projection is a bit more tricky. However, this is where polymake shows its real strength. Your observation that the naive projection is a bit hard means that finding the facets via Fourier-Motzkin is not easy (maybe impossible; don't know). Here is how polymake does it in an instant:

Code: Select all

> prefer_now "lrs"; print $q->FACETS; -5 7 0 0 0 0 0 0 0 0 -1 0 0 0 0 6 0 0 0 0 1 0 -1 0 0 0 0 0 0 0 1 0 0 -1 0 0 0 0 0 0 1 0 0 0 -1 0 0 0 0 0 1 0 0 0 0 0 -1 0 0 0 -3 0 0 0 0 0 0 0 4 5 1 0 0 0 0 0 0 -1 0 0 -1 0 0 0 0 0 0 5 4 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 -1 -3 0 0 0 0 6 5 0 0 5 1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 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 0 1 -2 0 5 0 0 0 5 0 0 5 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -1 0 0 0 0
That is, we employ the reverse search method (implemented in lrslib), and this can do the computation easily.

There was nothing wrong, neither in your way of using polymake, nor with the software itself. You just hit upon a problem which requires some more geometric insight. If you want to know more about such things, please, look into our paper
Computing convex hulls and counting integer points with polymake and the associated web page.

Re: Error when using projection command

Posted: 08 Feb 2018, 04:51
by soheilmn
Many thanks to gawrilow and joswig.

@joswig: I really appreciate your detailed answer; it helped me a lot in understanding what's going on.