Multiset Ordering Constraints

Alan M. Frisch; Ian Miguel; Zeynep Kiziltan; Brahim Hnich; Toby Walsh

Multiset Ordering Constraints

Alan M. Frisch, Ian Miguel, Zeynep Kiziltan, Brahim Hnich, Toby Walsh

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

We identify a new and important global (or non-binary) constraint. This constraint ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is useful for a number of different applications including breaking symmetry and fuzzy constraint satisfaction. We propose and implement an efficient linear time algorithm for enforcing generalised arc consistency on such a multiset ordering constraint. Experimental results on several problem domains show considerable promise.

Original language	Undefined/Unknown
Pages (from-to)	299-328
Number of pages	30
Journal	CoRR
Volume	abs/0905.3769
Issue number	2
Publication status	Published - Feb 2009

Access to Document

http://arxiv.org/abs/0905.3769

Cite this

@article{517c9c2ee38c4237a6a3d866878a472b,

title = "Multiset Ordering Constraints",

abstract = "We identify a new and important global (or non-binary) constraint. This constraint ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is useful for a number of different applications including breaking symmetry and fuzzy constraint satisfaction. We propose and implement an efficient linear time algorithm for enforcing generalised arc consistency on such a multiset ordering constraint. Experimental results on several problem domains show considerable promise. ",

author = "Frisch, {Alan M.} and Ian Miguel and Zeynep Kiziltan and Brahim Hnich and Toby Walsh",

year = "2009",

month = feb,

language = "Undefined/Unknown",

volume = "abs/0905.3769",

pages = "299--328",

journal = "CoRR",

number = "2",

}

TY - JOUR

T1 - Multiset Ordering Constraints

AU - Frisch, Alan M.

AU - Miguel, Ian

AU - Kiziltan, Zeynep

AU - Hnich, Brahim

AU - Walsh, Toby

PY - 2009/2

Y1 - 2009/2

N2 - We identify a new and important global (or non-binary) constraint. This constraint ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is useful for a number of different applications including breaking symmetry and fuzzy constraint satisfaction. We propose and implement an efficient linear time algorithm for enforcing generalised arc consistency on such a multiset ordering constraint. Experimental results on several problem domains show considerable promise.

AB - We identify a new and important global (or non-binary) constraint. This constraint ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is useful for a number of different applications including breaking symmetry and fuzzy constraint satisfaction. We propose and implement an efficient linear time algorithm for enforcing generalised arc consistency on such a multiset ordering constraint. Experimental results on several problem domains show considerable promise.

UR - http://www.scopus.com/inward/record.url?scp=57749092641&partnerID=8YFLogxK

M3 - Article

VL - abs/0905.3769

SP - 299

EP - 328

JO - CoRR

JF - CoRR

IS - 2

ER -

Multiset Ordering Constraints

Abstract

Access to Document

Other files and links

Cite this