Name
Abstract | ||
|---|---|---|
A global cardinality constraint (gcc) is specified in terms of a set of variables iX={ix1,…,ixp} which take their values in a subset of iV={iv1,…,ivd}. It constrains the number of times each value ivi∈iV is assigned to a variable in iX to be in an interval [ili,iui]. A gcc with costs (costgcc) is a generalization of a gcc in which a cost is associated with each value of each variable. Then, each solution of the underlying gcc is associated with a global cost equal to the sum of the costs associated with the assigned values of the solution. A costgcc constrains the global cost to be less than a given value. Cardinality constraints with costs have proved very useful in many real-life problems, such as traveling salesman problems, scheduling, rostering, or resource allocation. For instance, they are useful for expressing preferences or for defining constraints such as a constraint on the sum of all different variables. In this paper, we present an efficient way of implementing arc consistency for a costgcc. We also study the incremental behavior of the proposed algorithm. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1023/A:1020506526052 | Constraints |
Keywords | Field | DocType |
constraint satisfaction problem,global constraint,filtering algorithm,cardinality constraints,cardinality constraints with costs,arc consistency | Discrete mathematics,Local consistency,Mathematical optimization,Scheduling (computing),Cardinality,Constraint satisfaction problem,Resource allocation,Travelling salesman problem,Mathematics | Journal |
Volume | Issue | ISSN |
7 | 3/4 | 1572-9354 |
Citations | PageRank | References |
25 | 1.36 | 5 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jean-charles Régin | 1 | 1312 | 96.59 |