Polyhedron manipulation in Python
This library allows common operations over convex polyhedra such as polytope projection and vertex enumeration.
See the API documentation for details.
Installation
Install system packages (here for Debian-based distributions) for Python and GLPK by:
$ sudo apt-get install cython libglpk-dev python python-dev python-pip python-scipyThen, install the library by:
$ pip install pypomanExamples
Vertex enumeration
We can compute the list of vertices of a polytope described in halfspace representation by
import numpy as np
from pypoman import compute_polytope_vertices
A = np.array([
[-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1],
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
[1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1]])
b = np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 2, 2, 1, 2, 3])
vertices = compute_polytope_vertices(A, b)Halfspace enumeration
The other way round, assume we know the vertices of a polytope, and want to get its halfspace representation
import numpy as np
from pypoman import compute_polytope_halfspaces
vertices = map(
np.array,
[[1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1], [0, 1, 1]],
)
A, b = compute_polytope_halfspaces(vertices)Polytope projection
Let us project an
from numpy import array, eye, ones, vstack, zeros
from pypoman import plot_polygon, project_polytope
n = 10 # dimension of the original polytope
p = 2 # dimension of the projected polytope
# Original polytope:
# - inequality constraints: \forall i, |x_i| <= 1
# - equality constraint: sum_i x_i = 0
A = vstack([+eye(n), -eye(n)])
b = ones(2 * n)
C = ones(n).reshape((1, n))
d = array([0])
ineq = (A, b) # A * x <= b
eq = (C, d) # C * x == d
# Projection is proj(x) = [x_0 x_1]
E = zeros((p, n))
E[0, 0] = 1.
E[1, 1] = 1.
f = zeros(p)
proj = (E, f) # proj(x) = E * x + f
vertices = project_polytope(proj, ineq, eq, method='bretl')
if __name__ == "__main__": # plot projected polytope
import pylab
pylab.ion()
pylab.figure()
plot_polygon(vertices)See also
- A short introduction to Polyhedra and polytopes
- Komei Fukuda's Frequently Asked Questions in Polyhedral Computation
- The Polyhedron class in Sage
- StabiliPy: a Python package implementing a more general recursive method for polytope projection
