## Error when using projection command

Questions and problems about using polymake go here.

Moderator: Moderators

soheilmn
Posts: 2
Joined: 01 Feb 2018, 23:49

### Error when using projection command

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. Attachments fcnf.lp (1003 Bytes) Downloaded 86 times gawrilow Main Author Posts: 349 Joined: 25 Dec 2010, 17:40 ### Re: Error when using projection command 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... joswig Main Author Posts: 216 Joined: 24 Dec 2010, 11:10 ### Re: Error when using projection command 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.

soheilmn
Posts: 2
Joined: 01 Feb 2018, 23:49

### Re: Error when using projection command

Many thanks to gawrilow and joswig.

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