Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
The Conjunction of Interval Among Constraints
verfasst von : Gilles Chabert, Sophie Demassey
Erschienen in: Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
An
Among
constraint holds if the number of variables that belong to a given value domain is between given bounds. This paper focuses on the case where the variable and value domains are intervals. We investigate the conjunction of
Among
constraints of this type. We prove that checking for satisfiability – and thus, enforcing bound consistency – can be done in polynomial time. The proof is based on a specific decomposition that can be used as such to filter inconsistent bounds from the variable domains. We show that this decomposition is incomparable with the natural conjunction of
Among
constraints, and that both decompositions do not ensure bound consistency. Still, experiments on randomly generated instances reveal the benefits of this new decomposition in practice. This paper also introduces a generalization of this problem to several dimensions and shows that satisfiability is
$\mathcal{R}$
-complete in the multi-dimensional case