passagemath-polyhedra 10.4.65

passagemath: Convex polyhedra in arbitrary dimension, mixed integer linear optimization

About SageMath

“Creating a Viable Open Source Alternative to

Magma, Maple, Mathematica, and MATLAB”

Copyright (C) 2005-2024 The Sage Development Team

https://www.sagemath.org

SageMath fully supports all major Linux distributions, recent versions of macOS, and Windows (Windows Subsystem for Linux).

See https://doc.sagemath.org/html/en/installation/index.html for general installation instructions.

About this pip-installable distribution

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

• Python backend for polyhedra over general ordered fields

• Linear, Mixed Integer Linear, and Semidefinite Optimization frontends

• GNU Linear Programming Kit (GLPK) backend for large-scale linear and mixed integer linear optimization (floating point arithmetic)

• Interactive Simplex Method

• 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]”

Toric varieties

$ 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]”

Polymake, via JuPyMake

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]”

SCIP Mixed Integer Optimization solver, via PySCIPOpt

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