Efficient Operations On MDDs for Building Constraint Programming Models
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 374-379.
Abstract
We propose improved algorithms for defining the most common operations on Multi-Valued Decision Diagrams (MDDs): creation, reduction, complement, intersection, union, difference, symmetric difference, complement of union and complement of intersection. Then, we show that with these algorithms and thanks to the recent development of an efficient algorithm establishing arc consistency for MDD based constraints (MDD4R), we can simply solve some problems by modeling them as a set of operations between MDDs. We apply our approach to the regular constraint and obtain competitive results with dedicated algorithms. We also experiment our technique on a large scale problem: the phrase generation problem and we show that our approach gives equivalent results to those of a specific algorithm computing a complex automaton.
@inproceedings{ijcai2015p59,
title = {Efficient Operations On MDDs for Building Constraint Programming Models},
author = {Perez, Guillaume and Régin, Jean-Charles},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {374--379},
year = {2015},
month = {7},
note = {Main Track},
url = {https://ijcai.org/proceedings/2015/59},
}
TY - CPAPER TI - Efficient Operations On MDDs for Building Constraint Programming Models AU - Perez, Guillaume AU - Régin, Jean-Charles T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 374 EP - 379 UR - https://ijcai.org/proceedings/2015/59 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
