Could Polymake solve a 20-dimension problem?

Questions and problems about using polymake go here.
jgan
Posts: 2
Joined: 24 Jun 2013, 13:04

Could Polymake solve a 20-dimension problem?

Postby jgan » 24 Jun 2013, 13:16

I'm working on a Facet enumeration problem in around 20 dimension, and the number of input vertexes is around 2^20, could Polymake solve such a high dimensional problem?

I tried to solve it with Polymake, but there's just no any output when I typed in my code. It seems that it was calculating, but there was no any output after hours, and I could know from nowhere the calculating progress. It works well with less inputs and low dimension, so I guess my code is all right.

Dose anybody have any idea on this? Many thanks!

herr
Developer
Posts: 40
Joined: 30 Dec 2010, 13:15

Re: Could Polymake solve a 20-dimension problem?

Postby herr » 25 Jun 2013, 13:49

It is hard to predict whether polymake (or any convex hull code) is able to cope with a polytope in dimension 20 given by such a lot of points. The resulting number of facets could be incredibly large, see also the discussion in this post. It really depends very much on the specific properties of your polytope. Maybe you should compute the facets of a smaller instance, and then try to analyze the structure of the polytope. Also notice that polymake offers three different convex hull codes which behave quite differently. I'd suggest to test cdd or lrs on your instances via

Code: Select all

prefer "lrs";
or

Code: Select all

prefer "cdd";

jgan
Posts: 2
Joined: 24 Jun 2013, 13:04

Re: Could Polymake solve a 20-dimension problem?

Postby jgan » 30 Jun 2013, 10:27

Thanks very much for your advices!

Now I realize that it's really unpredictable for such large dimension. I'm thinking about using approximation for my problem.


Return to “Helpdesk”