Automatic Synthesis of Smart Table Constraints by Abstraction of Table Constraints

Automatic Synthesis of Smart Table Constraints by Abstraction of Table Constraints

Baudouin Le Charlier, Minh Thanh Khong, Christophe Lecoutre, Yves Deville

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 681-687. https://doi.org/10.24963/ijcai.2017/95

The smart table constraint represents a powerful modeling tool that has been recently introduced. This constraint allows the user to represent compactly a number of well-known (global) constraints and more generally any arbitrarily structured constraints, especially when disjunction is at stake. In many problems, some constraints are given under the basic and simple form of tables explicitly listing the allowed combinations of values. In this paper, we propose an algorithm to convert automatically any (ordinary) table into a compact smart table. Its theoretical time complexity is shown to be quadratic in the size of the input table. Experimental results demonstrate its compression efficiency on many constraint cases while showing its reasonable execution time. It is then shown that using filtering algorithms on the resulting smart table is more efficient than using state of the art filtering algorithms on the initial table.
Keywords:
Constraints and Satisfiability: Constraint Satisfaction
Constraints and Satisfiability: Global Constraints
Combinatorial & Heuristic Search: Heuristic Search