Getting Started

Overview

pycddlib is a Python wrapper for Komei Fukuda’s cddlib.

cddlib is an implementation of the Double Description Method of Motzkin et al. for generating all vertices (i.e. extreme points) and extreme rays of a general convex polyhedron given by a system of linear inequalities.

The program also supports the reverse operation (i.e. convex hull computation). This means that one can move back and forth between an inequality representation and a generator (i.e. vertex and ray) representation of a polyhedron with cdd. Also, it can solve a linear programming problem, i.e. a problem of maximizing and minimizing a linear function over a polyhedron.

Installation

Automatic Installer

The simplest way to install pycddlib is to install it with pip:

pip install pycddlib

On Windows, this will install from a binary wheel (for Python 3.7 to 3.11; for other versions of Python you will need to build from source, see below).

On Linux and Mac, this will install from source, and you will need GMP as well as the Python development headers. Your distribution probably has pre-built packages for it. For example, on Fedora, install it by running:

dnf install gmp-devel python3-devel

whilst on Ubuntu:

apt-get install libgmp-dev python3-dev

and on Mac:

brew install gmp

Building From Source

Full build instructions are in the git repository, under build.yml.

For Windows, you must take care to use a compiler and platform toolset that is compatible with the one that was used to compile Python. For Python 3.7 to 3.11, you can use Visual Studio 2022 with platform toolset v143.

Next, you must build MPIR using its provided project file. For instance, for Python 3.7 to 3.11, this should work:

Invoke-WebRequest -Uri "https://github.com/wbhart/mpir/archive/refs/heads/mpir-3.0.0.zip" -OutFile "mpir-3.0.0.zip"
Expand-Archive mpir-3.0.0.zip
msbuild mpir-3.0.0\mpir-mpir-3.0.0\build.vc14\lib_mpir_gc\lib_mpir_gc.vcxproj /p:Configuration=Release /p:Platform=x64 /p:PlatformToolset=v143

When building pycddlib, to tell Python where MPIR is located on your Windows machine, you can use:

python setup.py build build_ext -I<mpir_include_folder> -L<mpir_lib_folder>