×

zbMATH — the first resource for mathematics

Enforcing arc consistency on global constraints by solving subproblems on the fly. (English) Zbl 0961.68124
Jaffar, Joxan (ed.), Principles and practice of constraint programming - CP ’99. 5th international conference, Alexandria, VA, USA, October 11-14, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1713, 103-117 (1999).
Summary: Constraint networks are used more and more to solve combinatorial problems in real-life applications. As pointed out by the authors in “Arc consistency for general constraint networks: preliminary results [Proceedings of IJCAI ’97, Nagoya, 398-404 (1997)], this success requires dealing with non-binary constraints, which are widely needed in real world constraint solvers. Since arc consistency is a fundamental piece of reasoning that seems to be of great help during search for solutions, it is important to have efficient arc consistency algorithms for non-binary constraints. In this paper, we propose a new instantiation of GAC-schema that achieves arc consistency on global constraints (sets of original constraints taken globally). This algorithm, which searches for supports on these global constraints by solving the corresponding subproblem on the fly, outperforms the previous available techniques, such as GAC-schema and its instantiation to predicates. It can simultaneously take into account the multidirectionality of the global constraint, and take advantage of the knowledge of the constraints of the subproblem. Furthermore, we show on several experiments the interest of our approach for problem modeling.
For the entire collection see [Zbl 0929.00071].

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite