My polymake is running for more than 12hours

General discussion on polymake goes here.
paulcheung
Posts: 14
Joined: 06 Oct 2020, 03:45

My polymake is running for more than 12hours

Postby paulcheung » 09 Apr 2022, 04:32

Hi, I have a problem. I run my code. However, it has been 12 hours and there is not any result. I was trying to convert a polytope defined by inequalities into vertices.

There are over 200 inequalities, which has 70 dimensions. However, most are 0 and 1.

Is it normal that it took so long? I check my task manager and the ubuntu (for windows) is not taking any CPU and only small amount of Memory (~2MB). Is there anyway I can allocate more power to it so that it is faster?

Thank you in advance!

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

Re: My polymake is running for more than 12hours

Postby joswig » 11 Apr 2022, 16:45

A polytope in 70 dimensions with 200 inequalities may have as many as 983858800923516812309510979394668240 vertices (by McMullen's upper bound theorem). Of course that number can also be much smaller. In general, there is no good way to tell ahead of time if such a computation is possible and how long it will take (if it is finished before our known universe will come to its end).

I should add: even if that number would be smaller, there is no algorithm known which computes the convex hull in polynomial time (measured in the combined size of the input and the output).

My best offer is a comprehensive set of tests documented in:
  • Benjamin Assarf, Ewgenij Gawrilow, Katrin Herr, Michael Joswig, Benjamin Lorenz, Andreas Paffenholz and Thomas Rehn. Computing convex hulls and counting integer points with polymake. Math. Program. Comput. 9 (2017), no. 1, 1-38. doi:10.1007/s12532-016-0104-z
This should give you a (very vague) idea what can be computed within a reasonable amount of time.
See also this thread; you will find more of the same in this forum.


Return to “General Discussion”