Decision Diagrams for Discrete Optimization in Julia.
Provides a generic implementation of decision diagrams (top-down construction of layered state transition graph). Implements a branch-and-bound algorithms with subproblems defined by nodes in an exact cutset of the diagram.
To support new problem classes, several methods have to be implemented that are dispatched on the user-defined types for the instance, describing the states and transitions.
The solver behavior (restrictions, relaxations, variable order, diagram width) can be fully customized through user-defined layer processing.
The package is mostly written as a learning experiment. The appeal (for me) of using decision diagrams to solve discrete optimization problems is two-fold:
- The simplicity of the algorithm makes implementation from scratch a reasonable endeavor.
- It seems that the DD-based branch-and-bound lends itself to parallelization, yielding better speed-ups than MIP solvers.
This is (still) mostly a naive text book implementation. I'm sure there's room for improvement in the choice of data structures and avoiding frequent allocations.
It's currently assumed that the objective function is to be maximized, and the transition values are combined by addition. That is, we're looking for a longest path in the diagram, using as arc weights the values of the transitions. In principle, one could also choose minimization or use another operator (multiplication, maximum), but this would require even more type parametrization.
The decision diagram does not keep all transition arcs, but computes the longest path on the fly. That is, after a new layer is created, each node only remembers a single ingoing arc. This simplification works OK for the purpose of finding an optimal solution, but it rules out other use cases such as the enumeration of feasible solutions or post-optimality analysis.
Models and methods for some specific problem classes are implemented in the context of this package as submodules. The main motivation is to test-drive the current API, to make sure it's sufficiently general and not too verbose.
Currently included are:
- Binary Knapsack Problem.
- Set Cover Problem.
- Index Fund Construction (as defined in Optimization Methods in Finance)
The implementation is informed by the book Decision Diagrams for Optimization by D Bergman, A Cire, WJ van Hoeve and J Hooker.
The MDD website also contains a lot of valuable resources, in particular the INFORMS article Discrete Optimization with Decision Diagrams.
Pull requests with various forms of contributions are very welcome. In particular, I would appreciate suggestions to simplify the current interface, improve overall performance or cover more problem classes.
- DDX10: Parallel branch-and-bound (C++, X10).
- ryanjoneil/tsppd-dd: TSP with pickup and delivery times (Go).
- rkimura47/pymdd: Generic implementation of MDDs (Python).
- ac-tuwien/pymhlib: DD-based relaxation (Python).
- vcoppe/mdd-solver: Generic solver library (Java).
- xgillard/ddo: Generic solver (Rust).