English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Cost-filtering Algorithms for the two Sides of the Sum of Weights of Distinct Values Constraint

Beldiceanu, N., Carlsson, M., & Thiel, S.(2002). Cost-filtering Algorithms for the two Sides of the Sum of Weights of Distinct Values Constraint (SICS-T-2002:14-SE). Uppsala, Sweden: Swedish Institute of Computer Science.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Beldiceanu, Nicolas1, Author
Carlsson, Mats1, Author
Thiel, Sven2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 2002
 Publication Status: Issued
 Pages: -
 Publishing info: Uppsala, Sweden : Swedish Institute of Computer Science
 Table of Contents: -
 Rev. Type: -
 Identifiers: Report Nr.: SICS-T-2002:14-SE
BibTex Citekey: BCT2002:SumOfWeights
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: SICS Technical Report
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: Kista : Swedish Institute of Computer Science
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: ISSN: 1100-3154