By the same authors

From the same journal

From the same journal

Filtering algorithms for the multiset ordering constraint

Research output: Contribution to journalArticle

Author(s)

Department/unit(s)

Publication details

JournalArtificial Intelligence
DatePublished - Feb 2009
Issue number2
Volume173
Number of pages30
Pages (from-to)299-328
Original languageEnglish

Abstract

Constraint programming (CP) has been used with great success to tackle a wide variety of constraint satisfaction problems which are computationally intractable in general. Global constraints are one of the important factors behind the success of CP. In this paper, we study a new global constraint, the multiset ordering constraint, which is shown to be useful in symmetry breaking and searching for leximin optimal solutions in CP. We propose efficient and effective filtering algorithms for propagating this global constraint. We show that the algorithms maintain generalised arc-consistency and we discuss possible extensions. We also consider alternative propagation methods based on existing constraints in CP toolkits. Our experimental results on a number of benchmark problems demonstrate that propagating the multiset ordering constraint via a dedicated algorithm can be very beneficial. (C) 2008 Elsevier B.V. All rights reserved.

    Research areas

  • Constraint satisfaction, Constraint programming, Modelling, Global constraints, Constraint propagation, Propagation algorithms, Symmetry breaking, Multiset ordering, Leximin optimal solutions, GLOBAL CARDINALITY CONSTRAINT, CONSISTENCY

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations