ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 13 Feb 2017 17:29:55 +0100highest dimension polyhedronhttps://ask.sagemath.org/question/36510/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,
Thu, 09 Feb 2017 20:20:49 +0100https://ask.sagemath.org/question/36510/highest-dimension-polyhedron/Comment by mforets for <p>Hi,</p>
<p>I use the command Polyhedron(vertices = points) where points is an array to create a polyhedron in sage.</p>
<p>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.</p>
<p>However, when the dimension increases over 12, things get really slow.</p>
<p>So what is the highest dimension polyhedron that sage can handle?</p>
<p>Thanks,</p>
https://ask.sagemath.org/question/36510/highest-dimension-polyhedron/?comment=36597#post-id-36597just 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)](http://people.ee.ethz.ch/~mpt/3/).Mon, 13 Feb 2017 13:08:41 +0100https://ask.sagemath.org/question/36510/highest-dimension-polyhedron/?comment=36597#post-id-36597Comment by moati for <p>Hi,</p>
<p>I use the command Polyhedron(vertices = points) where points is an array to create a polyhedron in sage.</p>
<p>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.</p>
<p>However, when the dimension increases over 12, things get really slow.</p>
<p>So what is the highest dimension polyhedron that sage can handle?</p>
<p>Thanks,</p>
https://ask.sagemath.org/question/36510/highest-dimension-polyhedron/?comment=36603#post-id-36603I use the Hrep of these points as a part of an MILP model in my optimization problemMon, 13 Feb 2017 16:12:00 +0100https://ask.sagemath.org/question/36510/highest-dimension-polyhedron/?comment=36603#post-id-36603Comment by mforets for <p>Hi,</p>
<p>I use the command Polyhedron(vertices = points) where points is an array to create a polyhedron in sage.</p>
<p>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.</p>
<p>However, when the dimension increases over 12, things get really slow.</p>
<p>So what is the highest dimension polyhedron that sage can handle?</p>
<p>Thanks,</p>
https://ask.sagemath.org/question/36510/highest-dimension-polyhedron/?comment=36607#post-id-36607@moati ok, I see, so in that case the Vrep-Hrep conversions are required.Mon, 13 Feb 2017 17:29:55 +0100https://ask.sagemath.org/question/36510/highest-dimension-polyhedron/?comment=36607#post-id-36607Answer by Dima for <p>Hi,</p>
<p>I use the command Polyhedron(vertices = points) where points is an array to create a polyhedron in sage.</p>
<p>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.</p>
<p>However, when the dimension increases over 12, things get really slow.</p>
<p>So what is the highest dimension polyhedron that sage can handle?</p>
<p>Thanks,</p>
https://ask.sagemath.org/question/36510/highest-dimension-polyhedron/?answer=36515#post-id-36515this 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)
Thu, 09 Feb 2017 21:27:16 +0100https://ask.sagemath.org/question/36510/highest-dimension-polyhedron/?answer=36515#post-id-36515Comment by moati for <p>this depends on the input quite a bit. Namely, the following factors play a big role:</p>
<ul>
<li>how many facets your polytope $P$ has</li>
<li>how big in abs. value the coordinates of your points are (assuming they are all integers)</li>
<li>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)</li>
</ul>
https://ask.sagemath.org/question/36510/highest-dimension-polyhedron/?comment=36526#post-id-36526My 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,Fri, 10 Feb 2017 00:20:09 +0100https://ask.sagemath.org/question/36510/highest-dimension-polyhedron/?comment=36526#post-id-36526Comment by Dima for <p>this depends on the input quite a bit. Namely, the following factors play a big role:</p>
<ul>
<li>how many facets your polytope $P$ has</li>
<li>how big in abs. value the coordinates of your points are (assuming they are all integers)</li>
<li>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)</li>
</ul>
https://ask.sagemath.org/question/36510/highest-dimension-polyhedron/?comment=36572#post-id-36572no, 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.Sat, 11 Feb 2017 19:27:00 +0100https://ask.sagemath.org/question/36510/highest-dimension-polyhedron/?comment=36572#post-id-36572