Change search
ReferencesLink to record
Permanent link

Direct link
Sweep as a generic pruning technique applied to constraint relaxation
Number of Authors: 2
2001 (English)Conference paper (Refereed)
Abstract [en]

We introduce a new generic filtering algorithm for handling constraint relaxation within constraint programming. More precisely, we first present a generic pruning technique, which is useful for a special case of the cardinality operator where all the constraints have at least two variables in common. This method is based on a generalisation of a sweep algorithm, which handles a conjunction of constraints to the case where one just knows the minimum and maximum number of constraints that have to hold. The main benefit of this new technique comes from the fact that, even if we don't know which, and exactly how many constraints, will hold in the final solution, we can still prune the variables of those constraints right from the beginning according to the minimum and maximum number of constraints that have to hold. We then show how to extend the previous sweep algorithm in order to handle preferences among constraints. Finally, we specialise this technique to an extension of the non-overlapping rectangles constraint, where we permit controlling how many non-overlapping constraints should hold. This allows handling over-constrained placement problems and provides constraint propagation even if some non-overlapping constraints have to be relaxed.

Place, publisher, year, edition, pages
2001, 1.
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-22596OAI: oai:DiVA.org:ri-22596DiVA: diva2:1042161
Conference
Soft'01 workshop at CP'2001, International conference on Principles and Practice of Constraint Programming
Available from: 2016-10-31 Created: 2016-10-31

Open Access in DiVA

fulltext(102 kB)1 downloads
File information
File name FULLTEXT01.pdfFile size 102 kBChecksum SHA-512
a70b7ebcc0a7a2cc9878da22454fc2d994c7b9e00822f043d344bbdab26895ecf690264422742f93c06163c6b78008f83b724f7f109c4bd4aa2bf7f795bed90f
Type fulltextMimetype application/pdf
fulltext(621 kB)0 downloads
File information
File name FULLTEXT02.psFile size 621 kBChecksum SHA-512
c59c82048f9e1749b9e391a2a269eeec73e3d4d724016f84696485a1a98121a2cf511c84f1f520230850622a1c801ccc9d85626cc075ec9d83b633ee91b6a48b
Type fulltextMimetype application/postscript

Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 1 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 5 hits
ReferencesLink to record
Permanent link

Direct link