Ddo, a Generic and Efficient Framework for MDD-Based Optimization

Xavier Gillard, Pierre Schaus, Vianney CoppéIJCAI 2020 · DOI

TL;DR

This paper introduces ddo, a new open-source Rust library that provides a generic and efficient framework for solving combinatorial optimization problems using Multivalued Decision Diagrams (MDDs). By implementing a branch-and-bound approach on MDDs, ddo aims to make this powerful technique more accessible and applicable to a wider range of problems, demonstrating competitive performance against existing solvers.

What Problem Does This Paper Address?

Combinatorial optimization problems, which involve finding the best solution from a finite set of possibilities, are notoriously difficult to solve. While techniques like dynamic programming (DP) can be effective, their direct application often leads to computationally intractable models. Decision Diagrams (DDs), and specifically Multivalued Decision Diagrams (MDDs), offer a way to represent the solution space of DP problems compactly. However, constructing exact DDs can still be exponentially expensive. Decision Diagram-Based Optimization (DDO) uses approximate DDs (relaxed and restricted) to bound the solution space and find optimal solutions. The challenge addressed here is the lack of a readily available, generic, and efficient framework that allows researchers and practitioners to easily leverage MDD-based optimization for various problems, often requiring significant custom implementation.

Methods

The core of ddo is its implementation of a generic branch-and-bound algorithm that operates on MDDs. This framework takes a problem's DP formulation (defined by its state, initial state, transition function, and cost function) and a relaxation strategy as input. The relaxation is crucial for creating bounded-size MDDs (specifically, relaxed MDDs which provide an upper bound on the optimal solution). The library allows for custom heuristics but also provides defaults. The framework is built in Rust, emphasizing efficiency and leveraging parallel computing capabilities. The paper highlights that users only need to provide the DP formulation and a relaxation, making it significantly easier to apply DDO to new problems.

Datasets

The paper evaluates ddo on instances from the DIMACS challenge for the Maximum Independent Set problem (MISP) and the Maximum Clique problem. These are standard benchmarks used in the field. No new datasets were introduced.

Key Insights and Ideas

  • Genericity is Key: The primary insight is that a generic framework for MDD-based optimization is feasible and highly beneficial. By abstracting away the problem-specific details into DP formulations and relaxations, ddo allows for broad applicability.
  • Branch-and-Bound on MDDs: The paper demonstrates the effectiveness of combining the branch-and-bound search strategy with the compact representation offered by MDDs for optimization.
  • Accessibility of DDO: ddo significantly lowers the barrier to entry for using DDO techniques, which have previously shown state-of-the-art performance but required substantial custom development.
  • Parallelism Built-in: The framework is designed to easily exploit multi-core processors, offering a significant speedup for computationally intensive tasks.

Key Results

The experimental results show that ddo achieves competitive performance on MISP/Max-Clique instances from the DIMACS challenge. When run on a machine with 32 hardware threads, ddo significantly outperforms its single-threaded execution, often by an order of magnitude. For example, the hamming8-4.clq instance was solved in 2.17 seconds with 32 threads, compared to 25.45 seconds with 1 thread. The paper notes that these results are on par with specialized frameworks like DDX10, which have themselves been favorably compared to commercial solvers like IBM ILOG CPLEX.

Limitations and Future Work

The paper acknowledges that constructing DDs can still be memory-intensive, and while ddo aims for efficiency, memory constraints can still be a limiting factor for extremely large problems. The authors suggest that future work could involve exploring more advanced relaxation techniques and further optimizing the MDD construction and manipulation algorithms. The demonstration section also hints at future work in exploring different heuristics and tuning strategies for the solver.

Summary updated

BibTeX
@inproceedings{gillard2020ddo,
  author = {Xavier Gillard and Pierre Schaus and Vianney Coppé},
  title = {{Ddo, a Generic and Efficient Framework for MDD-Based Optimization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/757},
}
Figure