Change search
ReferencesLink to record
Permanent link

Direct link
Cost-Filtering Algorithms for the two Sides of the Sum of Weights of Distinct Values Constraint
Number of Authors: 3
2002 (English)Report (Refereed)
Abstract [en]

This article introduces the sum of weights of distinct values constraint, which can be seen as a generalization of the number of distinct values as well as of the alldifferent, and the relaxed alldifferent constraints. This constraint holds if a cost variable is equal to the sum of the weights associated to the distinct values taken by a given set of variables. For the first aspect, which is related to domination, we present four filtering algorithms. Two of them lead to perfect pruning when each domain variable consists of one set of consecutive values, while the two others take advantage of holes in the domains. For the second aspect, which is connected to maximum matching in a bipartite graph, we provide a complete filtering algorithm for the general case. Finally we introduce several generic deduction rules, which link both aspects of the constraint. These rules can be applied to other optimization constraints such as the minimum weight alldifferent constraint or the global cardinality constraint with costs. They also allow taking into account external constraints for getting enhanced bounds for the cost variable. In practice, the sum of weights of distinct values constraint occurs in assignment problems where using a resource once or several times costs the same. It also captures domination problems where one has to select a set of vertices in order to control every vertex of a graph.

Place, publisher, year, edition, pages
Swedish Institute of Computer Science , 2002, 1. , 46 p.
Series
SICS Technical Report, ISSN 1100-3154 ; 2002:14
Keyword [en]
Constraint Programming, Global Constraint, Cost-Filtering, Assignment, Domination, Bipartite Matching
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-21990OAI: oai:DiVA.org:ri-21990DiVA: diva2:1041532
Available from: 2016-10-31 Created: 2016-10-31

Open Access in DiVA

fulltext(486 kB)5 downloads
File information
File name FULLTEXT01.pdfFile size 486 kBChecksum SHA-512
e62c14e525f04b7c4d5af7c0e689051fb72cd0c7f7a5d47f7e40c88ba6da18804ae3fb01a10e03eeb30fe91dd659839bd2192f6763c11dc220258887b4951314
Type fulltextMimetype application/pdf

Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 5 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: 6 hits
ReferencesLink to record
Permanent link

Direct link