sagemath_polyhedra: Convex polyhedra in arbitrary dimension, mixed integer linear optimization¶
This pip-installable distribution passagemath-polyhedra is a distribution of a part of the Sage Library. It provides a small subset of the modules of the Sage library (“sagelib”, \(passagemath-standard\)), sufficient for computations with convex polyhedra in arbitrary dimension (in exact rational arithmetic), and linear and mixed integer linear optimization (in floating point arithmetic).
What is included¶
Combinatorial and Discrete Geometry: Polyhedra, lattice polyhedra, lattice points in polyhedra, triangulations, fans, polyhedral complexes, hyperplane arrrangements
Parma Polyhedra Library (PPL) backends for rational polyhedra, lattice polygons, lattice polytopes; via pplpy
Linear, Mixed Integer Linear, and Semidefinite Optimization frontends
see https://github.com/passagemath/passagemath/blob/main/pkgs/sagemath-polyhedra/MANIFEST.in
Examples¶
A quick way to try it out interactively:
$ pipx run --pip-args="--prefer-binary" --spec "passagemath-polyhedra[test]" ipython
In [1]: from sage.all__sagemath_polyhedra import *
In [2]: P = Polyhedron(ieqs=[[0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 1], [0, 0, 1, -1, -1, 1, 0], [0, 0, -1, 1, -1, 1, 0]], eqns=[[-31, 1, 1, 1, 1, 1, 1]]); P
Out[2]: A 5-dimensional polyhedron in QQ^6 defined as the convex hull of 7 vertices
In [3]: P.Vrepresentation()
Out[4]:
(A vertex at (31, 0, 0, 0, 0, 0),
A vertex at (0, 0, 0, 0, 0, 31),
A vertex at (0, 0, 0, 0, 31, 0),
A vertex at (0, 0, 31/2, 0, 31/2, 0),
A vertex at (0, 31/2, 31/2, 0, 0, 0),
A vertex at (0, 31/2, 0, 0, 31/2, 0),
A vertex at (0, 0, 0, 31/2, 31/2, 0))
Available as extras, from other distributions¶
Additional features¶
pip install "passagemath-polyhedra[graphs]"Face lattices, combinatorial polyhedra, graph-theoretic constructions
$ pipx run --pip-args="--prefer-binary" --spec "passagemath-polyhedra[graphs,test]" ipython In [1]: from sage.all__sagemath_polyhedra import * In [2]: c5_10 = Polyhedron(vertices = [[i, i**2, i**3, i**4, i**5] for i in range(1, 11)]); c5_10 Out[2]: A 5-dimensional polyhedron in ZZ^5 defined as the convex hull of 10 vertices In [3]: c5_10_fl = c5_10.face_lattice(); [len(x) for x in c5_10_fl.level_sets()] Out[3]: [1, 10, 45, 100, 105, 42, 1]
pip install "passagemath-polyhedra[graphs,groups]"Constructing symmetric polyhedra, computing automorphisms, lattice point counting modulo group actions
$ pipx run --pip-args="--prefer-binary" --spec "passagemath-polyhedra[graphs,groups,test]" ipython In [1]: from sage.all__sagemath_polyhedra import * In [2]: P24 = polytopes.twenty_four_cell(); P24 Out[2]: A 4-dimensional polyhedron in QQ^4 defined as the convex hull of 24 vertices In [3]: AutP24 = P24.restricted_automorphism_group(); AutP24.order() Out[3]: 1152
pip install "passagemath-polyhedra[toric]"-
$ pipx run --pip-args="--prefer-binary" --spec "passagemath-polyhedra[graphs,toric,test]" ipython In [1]: from sage.all__sagemath_polyhedra import * In [2]: TV3 = ToricVariety(NormalFan(lattice_polytope.cross_polytope(3))); TV3 Out[2]: 3-d toric variety covered by 6 affine patches In [3]: TV3.is_orbifold() Out[3]: False
pip install "passagemath-polyhedra[latte]"Installs LattE integrale for lattice point counting and volume computation using generating function techniques.
$ pipx run --pip-args="--prefer-binary" --spec "passagemath-polyhedra[latte,test]" ipython In [1]: from sage.all__sagemath_polyhedra import * In [2]: P = polytopes.cube() In [3]: P.integral_points_count() Out[3]: 27 In [4]: (1000000000*P).integral_points_count(verbose=True) This is LattE integrale... ... Total time:... Out[4]: 8000000012000000006000000001
Additional backends for polyhedral computations¶
pip install "passagemath-polyhedra[normaliz]"Normaliz, via PyNormaliz, provides very fast computations in particular for polyhedra with data in algebraic number fields.
$ pipx run --pip-args="--prefer-binary" --spec "passagemath-polyhedra[normaliz,test]" ipython In [1]: from sage.all__sagemath_polyhedra import * In [2]: gap_norm = polytopes.grand_antiprism(backend='normaliz'); gap_norm In [3]: gap_norm.f_vector()
pip install "passagemath-polyhedra[cddlib]"cddlib provides support for computations with polyhedra in floating-point arithmetic.
$ pipx run --pip-args="--prefer-binary" --spec "passagemath-polyhedra[cddlib,test]" ipython In [1]: from sage.all__sagemath_polyhedra import * In [2]: P1 = polytopes.regular_polygon(5, exact=False); P1 Out[2]: A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 5 vertices
pip install "passagemath-polyhedra[lrslib]"lrslib can be used for polytope volume computations and for enumerating Nash equilibria.
$ pipx run --pip-args="--prefer-binary" --spec "passagemath-polyhedra[flint,lrslib,test]" ipython In [1]: from sage.all__sagemath_polyhedra import * In [2]: A = matrix([[2, 1], [1, 5/2]]); B = matrix([[-1, 3], [2, 1]]) In [3]: g = NormalFormGame([A, B]); g.obtain_nash(algorithm='lrs') Out[3]: [[(1/5, 4/5), (3/5, 2/5)]]
pip install "passagemath-polyhedra[polymake]"-
This currently requires a separate installation of polymake.
Optional backends for optimization¶
pip install "passagemath-polyhedra[cbc]"COIN/OR CBC Mixed Integer Linear Optimization solver, via sage_numerical_backends_coin
pip install "passagemath-polyhedra[cplex]"CPLEX Mixed Integer Optimization solver (proprietary; requires licensed installation), via sage_numerical_backends_cplex
pip install "passagemath-polyhedra[cvxpy]"CVXPy as middle-end for various backends
pip install "passagemath-polyhedra[gurobi]"Gurobi Mixed Integer Optimization solver (proprietary; requires licensed installation), via sage_numerical_backends_gurobi
pip install "passagemath-polyhedra[scip]"
Development¶
$ git clone --origin passagemath https://github.com/passagemath/passagemath.git
$ cd passagemath
passagemath $ ./bootstrap
passagemath $ python3 -m venv polyhedra-venv
passagemath $ source polyhedra-venv/bin/activate
(polyhedra-venv) passagemath $ pip install -v -e pkgs/sagemath-polyhedra
Type¶
standard
Dependencies¶
$(PYTHON)
$(PYTHON_TOOLCHAIN)
cython: C-Extensions for Python, an optimizing static compiler
memory_allocator: An extension class to allocate memory easily with Cython
mpc: Arithmetic of complex numbers with arbitrarily high precision and correct rounding
mpfr: Multiple-precision floating-point computations with correct rounding
sagemath_glpk: Linear and mixed integer linear optimization backend using GLPK
Version Information¶
package-version.txt:
10.6.29
version_requirements.txt:
passagemath-polyhedra ~= 10.6.29.0
Installation commands¶
$ pip install passagemath-polyhedra~=10.6.29.0
$ sage -i sagemath_polyhedra
However, these system packages will not be used for building Sage
because spkg-configure.m4 has not been written for this package;
see upstream Issue #27330 for more information.