Coud Polymake solve 30 dimensional problem?

Questions and problems about using polymake go here.
anverhisham

Coud Polymake solve 30 dimensional problem?

Postby anverhisham » 10 Aug 2016, 20:21

I'm working on a Vertex enumeration problem in around 30 dimension, and the number of inequality constraints is around 90, could Polymake solve such a high dimensional problem? I'm using latest release 3.0.

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

Re: Coud Polymake solve 30 dimensional problem?

Postby joswig » 11 Aug 2016, 10:32

This is, in general, impossible to predict. For some more detailed comments please see our recent survey Computing convex hulls and counting integer points with polymake.

As one indication it is good to keep McMullen's Upper Bound Theorem in mind. This says that the number of faces of a polytope with n vertices in dimension d is bounded by the number of faces of the cyclic polytope with the same parameters. That bound is in the order of O(n^{d/2}). polymake can give you the exact figures as follows:

Code: Select all

polytope > print upper_bound_theorem(30,90)->F_VECTOR; 90 4005 117480 2555190 43949268 622614630 7471375560 77515521435 706252528630 5720645481903 41604694413840 273897571557780 1643385429346680 9038619861406740 45795673964460816 206486905920259815 781756532944153830 2385752683928728555 5773957004337548040 11054190819557635398 16774467561955932180 20207155658677703910 19297630096292837160 14525231744481419805 8515290614467632138 3808936775839012290 1256280961790695680 288095458157920080 41040228360889440 2736015224059296
That is to say, in the worst case, you could have as many as

Code: Select all

polytope > print convert_to<Float>(upper_bound_theorem(30,90)->F_VECTOR->[29]); 2.7360152240593e+15
vertices. That would be too many for most of today's computers.

However, you can always be lucky.

See also
viewtopic.php?f=8&t=344


Return to “Helpdesk”