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
URN: urn:nbn:se:ri:diva-14784OAI: diva2:1036078
Soft'01 workshop at CP'2001, International conference on Principles and Practice of Constraint Programming
Available from: 2016-10-13 Created: 2016-10-13

Open Access in DiVA

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

Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
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

ReferencesLink to record
Permanent link

Direct link