Length-lex bound consistency for knapsack constraints

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Length-lex bound consistency for knapsack constraints

Full text

Pdf (375 KB)

Source

Symposium on Applied Computing archive
Proceedings of the 2009 ACM symposium on Applied Computing table of contents

Honolulu, Hawaii

SESSION: Constraint solving and programming track table of contents

Pages 1397-1401

Year of Publication: 2009

ISBN:978-1-60558-166-8

Authors

Justin Yip	Brown University, Providence, RI
Pascal Van Hentenryck	Brown University, Providence, RI

Sponsor

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 21, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1529282.1529594 What is a DOI?

ABSTRACT

This paper considers the length-lex domain for set-variables in constraint programming which includes not only membership but also cardinality and lexicographic information. The paper studies how to enforce bound consistency on a knapsack constraint over a set variable in this domain and proposes a bound-consistency algorithm which runs in O(c log n) time with a one-time preprocessing cost O(cn²) when the constraint is posted.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Francisco Azevedo , Pedro Barahona, Modelling Digital Circuits Problems with Set Constraints, Proceedings of the First International Conference on Computational Logic, p.414-428, July 01, 2000
	2	Yuri Malitsky , Meinolf Sellmann , Willem-Jan Hoeve, Length-Lex Bounds Consistency for Knapsack Constraints, Proceedings of the 14th international conference on Principles and Practice of Constraint Programming, September 14-18, 2008, Sydney, Australia [doi>10.1007/978-3-540-85958-1_18]
	3	Gervet, C. 1997. Interval Propagation to Reason about Sets: Definition and Implementation of a Practical Language. In Constraints journal, volume 1(3). Kluwer.
	4	Gervet, C., Van Hentenryck, P. 2006. Length-Lex Ordering for Set CSPs. In Proc. AAAI'06.
	5	Puget, J-F. 1992. PECOS a High Level Constraint Programming Language In Proc. of Spicis.
	6	Andrew Sadler , Carmen Gervet, Enhancing set constraint solvers with lexicographic bounds, Journal of Heuristics, v.14 n.1, p.23-67, February 2008 [doi>10.1007/s10732-007-9028-0]
	7	Van Hentenryck, P., Yip, J., Gervet, C. and Dooms, G., 2008. Bound Consistency for Binary Length-Lex Set Constraints. In Proc. AAAI'08.