Ask Your Question

# 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

## Comments

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).

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

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

## 1 answer

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

## Comments

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,

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.

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2017-02-09 13:20:49 -0500

Seen: 66 times

Last updated: Feb 09 '17