# highest dimension polyhedron

Hi,

I use the command Polyhedron(vertices = points) where points is an array to create a polyhedron in sage.

It works quite well for dimensions up to 12, i.e., each point in points consists of 12 bits, as the command takes 2-3 minutes even if the size of points is really large.

However, when the dimension increases over 12, things get really slow.

So what is the highest dimension polyhedron that sage can handle?

Thanks,

edit retag close merge delete

just for curiosity: what are the operations that you have to do with these polytopes? and can they be performed only with the Vrep? I ask because in my case its exactly the opposite: for some operations (e.g. support function calculus) it's 'enough' to have the Hrep, so i'm interested in adding a flag that turns-off the automatic computation of the complementary representation.. that's the behavior, for instance, in Matlab's Multi-parametric toolbox (MPT).

( 2017-02-13 13:08:41 +0200 )edit

I use the Hrep of these points as a part of an MILP model in my optimization problem

( 2017-02-13 16:12:00 +0200 )edit

@moati ok, I see, so in that case the Vrep-Hrep conversions are required.

( 2017-02-13 17:29:55 +0200 )edit

Sort by » oldest newest most voted

this depends on the input quite a bit. Namely, the following factors play a big role:

• how many facets your polytope $P$ has
• how big in abs. value the coordinates of your points are (assuming they are all integers)
• how degenerate $P$ is; i.e. the maximal number of neighbours of a vertex of $P$ --- the more degenerate it is, the slower the facet enumeration)
more

My points are all in the form of (0,0,1,0,1,0....0,0) so in each coordinate they take either 0 or 1.

For the number of facets and how degenerate P is, I can't this info a priori, can I?

Thanks,

( 2017-02-10 00:20:09 +0200 )edit

no, not really. See https://arxiv.org/pdf/math/9909177.pdf for bounds and examples. E.g. in dimension 13 you might have more than 17000000 facets.

( 2017-02-11 19:27:00 +0200 )edit