Polyhedron Manipulation in Python
This library implements common operations over convex polyhedra such as polytope projection and vertex enumeration.
See the complete API documentation for details.
Installation
Make sure you have all system-wide dependencies by:
sudo apt-get install cython libglpk-dev python python-dev python-pip python-scipy
Then, install the module itself:
pip install pypoman
Examples
Vertex enumeration
We can compute the list of vertices of a polytope described in halfspace
representation by A * x <= b:
from numpy import array
from pypoman import compute_polytope_vertices
A = 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 = 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 A * x <= b.
from numpy import array
from pypoman import compute_polytope_halfspaces
vertices = map(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 n-dimensional polytope over x = [x_1 ... x_n] onto its first two coordinates proj(x) = [x_1 x_2]:
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