Ask Your Question
1

highest dimension polyhedron

asked 2017-02-09 13:20:49 -0600

moati gravatar image

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

mforets gravatar imagemforets ( 2017-02-13 06:08:41 -0600 )edit

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

moati gravatar imagemoati ( 2017-02-13 09:12:00 -0600 )edit

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

mforets gravatar imagemforets ( 2017-02-13 10:29:55 -0600 )edit

1 answer

Sort by ยป oldest newest most voted
0

answered 2017-02-09 14:27:16 -0600

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)
edit flag offensive delete link 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,

moati gravatar imagemoati ( 2017-02-09 17:20:09 -0600 )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.

Dima gravatar imageDima ( 2017-02-11 12:27:00 -0600 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

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

Seen: 51 times

Last updated: Feb 09