Soft and Cost MDD Propagators

Guillaume Perez, Jean-Charles RéginAAAI 2017 · DOI

Multi-valued Decision Diagrams (MDDs) have become a cornerstone in Constraint Programming (CP) for representing complex, non-linear constraints. By modeling valid solutions as paths in a directed acyclic graph, MDDs allow solvers to prune large portions of the search space efficiently. However, real-world applications often introduce two significant challenges: the need to optimize for path costs and the necessity of "softening" constraints when no perfectly valid solution exists. This paper presents novel propagators designed to handle these scenarios with unprecedented efficiency.

The Cost-MDD4R Propagator

A primary contribution of this work is the adaptation of the MDD4R algorithm to handle costs. Traditional incremental algorithms for MDDs often suffer from high overhead when updating data structures during search. The "secret sauce" of the proposed Cost-MDD4R is its "reset" strategy. Rather than performing complex incremental updates, the algorithm evaluates whether it is computationally cheaper to simply wipe a layer and rebuild it.

By maintaining shortest-path information (referred to as up and dn values) across the graph, Cost-MDD4R can prune any path that exceeds a predefined cost budget. This approach proves particularly effective in dynamic search environments where variable domains change frequently.

Softening Constraints for "Near-Miss" Solutions

In many practical scenarios, such as plagiarism-free text generation, constraints may be so restrictive that no solution satisfies every rule. In these cases, we seek "soft" constraints that minimize the number of violations (Hamming distance). The authors propose three distinct strategies for softening MDDs.

Softening via Transformation

The most intuitive approach involves transforming a standard MDD into a Cost-MDD by introducing "wildcard" arcs. In this model, standard arcs represent valid transitions with a cost of 0, while wildcard arcs (labeled *) represent a violation with a cost of 1.

Transformation of an MDD into a Cost-MDD using wildcard arcs (*).

This transformation allows any existing Cost-MDD propagator to solve the soft constraint problem without further modification, effectively treating "softness" as a graph property.

Softening via Intersection

The most technically advanced method involves the intersection of the original constraint MDD with a secondary MDD representing a sum constraint. This sum MDD tracks the total number of violations accumulated along a path.

Intersection of a constraint MDD with a sum MDD to track violations.

By intersecting these two structures, the solver "precomputes" the violation counts. The final layer of the resulting MDD explicitly represents the total number of violations, allowing for extremely rapid pruning during search.

Performance and Scalability

The proposed methods were evaluated using both synthetic random instances and a real-world text generation task based on the fables of Jean de La Fontaine. In the text generation problem—which requires balancing Markovian style with strict anti-plagiarism constraints—Cost-MDD4R consistently outperformed existing incremental algorithms like ev-mdd, often by several factors.

For smaller, highly constrained problems, the intersection method emerged as the clear winner, sometimes achieving speedups of an order of magnitude. However, this speed comes at a cost: memory. The intersection process significantly increases the size of the MDD. Experimental results showed that once the MDD size approached memory limits (approximately 1.7GB), the overhead of memory swapping made Cost-MDD4R the more robust choice.

Conclusion

This research demonstrates that by treating constraint violations as costs and leveraging efficient graph rebuilding strategies, we can significantly enhance the performance of MDD-based solvers. While the intersection method offers peak performance for moderately sized problems, Cost-MDD4R provides a scalable alternative for massive datasets. Future work will focus on reducing the memory footprint of intersected MDDs to bring their high-speed benefits to even larger problem domains.

Summary updated

BibTeX
@inproceedings{perez2017soft,
  author = {Guillaume Perez and Jean-Charles Régin},
  title = {{Soft and Cost MDD Propagators}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11130},
}
Figure