pymdd

A simple Python implementation of a multivalued decision diagram (MDD), for use in optimization. The code prioritizes transparency over speed so that the user can clearly see the effects of various operations performed by the MDD.

At present, it can do the following:

• Compile an exact MDD given a dynamic programming (DP) formulation of the problem.
• Compile a relaxed or reduced MDD given a DP formulation of the problem and node selection/merging rules.
• Compile an exact MDD representation (with canonical arc costs) given a list of paths and their corresponding weights.
• Filter and refine an existing MDD for a constraint given as a DP model.
• Perform a shortest/longest path computation over the MDD.
• Write the MDD to a GraphViz file for visualization.
• Save/load the MDD to a JSON file for archiving/reconstruction.

Installation

To install for all users, navigate to root directory and call

pip install .

If you only want to install locally, use virtualenv or venv (Python 3 only). Alternatively, you can perform the following steps manually:

1. Create a new directory named pymdd/ in your working directory.
2. Create a copy of mdd.py in pymdd/.
3. If you using Python 2, create an empty file called __init__.py in pymdd/ (this ensures that python will recognize mdd.py as a module).

Usage

After following the installation instructions, you can now import the module from your working directory by calling

from pymdd.mdd import *

The examples/ directory includes some sample scripts based on examples from the book Decision Diagrams for Optimization by Bergman, Cire, van Hoeve, and Hooker (Springer, 2016).

Documentation

The API documentation for this project is generated by Sphinx, and is hosted on the gh-pages branch of this repository at http://rkimura47.github.io/pymdd/. The docs/ directory contains the files used to generate this documentation.

License

This project is licensed under the MIT License.