5.142. global_cardinality_with_costs

DESCRIPTIONLINKSGRAPH
Origin

[Regin99a]

Constraint

πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš πš’πšπš‘_𝚌𝚘𝚜𝚝𝚜(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚,π™Όπ™°πšƒπšπ™Έπš‡,π™²π™Ύπš‚πšƒ)

Synonyms

𝚐𝚌𝚌𝚌, 𝚌𝚘𝚜𝚝_𝚐𝚌𝚌.

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš,πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-πšπšŸπšŠπš›)
π™Όπ™°πšƒπšπ™Έπš‡πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’-πš’πš—πš,πš“-πš’πš—πš,𝚌-πš’πš—πš)
π™²π™Ύπš‚πšƒπšπšŸπšŠπš›
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
|πš…π™°π™»πš„π™΄πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,[πšŸπšŠπš•,πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ])
πšπš’πšœπšπš’πš—πšŒπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
πš…π™°π™»πš„π™΄πš‚.πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽβ‰₯0
πš…π™°π™»πš„π™΄πš‚.πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽβ‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(π™Όπ™°πšƒπšπ™Έπš‡,[πš’,πš“,𝚌])
πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_𝚜𝚎𝚚(π™Όπ™°πšƒπšπ™Έπš‡,[πš’,πš“])
π™Όπ™°πšƒπšπ™Έπš‡.πš’β‰₯1
π™Όπ™°πšƒπšπ™Έπš‡.πš’β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
π™Όπ™°πšƒπšπ™Έπš‡.πš“β‰₯1
π™Όπ™°πšƒπšπ™Έπš‡.πš“β‰€|πš…π™°π™»πš„π™΄πš‚|
|π™Όπ™°πšƒπšπ™Έπš‡|=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|*|πš…π™°π™»πš„π™΄πš‚|
Purpose

Each value πš…π™°π™»πš„π™΄πš‚[i].πšŸπšŠπš• should be taken by exactly πš…π™°π™»πš„π™΄πš‚[i].πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. In addition the π™²π™Ύπš‚πšƒ of an assignment is equal to the sum of the elementary costs associated with the fact that we assign the i th variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection to the j th value of the πš…π™°π™»πš„π™΄πš‚ collection. These elementary costs are given by the π™Όπ™°πšƒπšπ™Έπš‡ collection.

Example
3,3,3,6,πšŸπšŠπš•-3πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-3,πšŸπšŠπš•-5πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-0,πšŸπšŠπš•-6πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-1,πš’-1πš“-1𝚌-4,πš’-1πš“-2𝚌-1,πš’-1πš“-3𝚌-7,πš’-2πš“-1𝚌-1,πš’-2πš“-2𝚌-0,πš’-2πš“-3𝚌-8,πš’-3πš“-1𝚌-3,πš’-3πš“-2𝚌-2,πš’-3πš“-3𝚌-1,πš’-4πš“-1𝚌-0,πš’-4πš“-2𝚌-0,πš’-4πš“-3𝚌-6,14

The πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš πš’πšπš‘_𝚌𝚘𝚜𝚝𝚜 constraint holds since:

  • Values 3, 5 and 6 respectively occur 3, 0 and 1 times within the collection 〈3,3,3,6βŒͺ.

  • The π™²π™Ύπš‚πšƒ argument corresponds to the sum of the costs respectively associated with the first, second, third and fourth items of 〈3,3,3,6βŒͺ, namely 4, 1, 3 and 6.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
|πš…π™°π™»πš„π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°π™»πš„π™΄πš‚.πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ)>1
πš›πšŠπš—πšπšŽ(π™Όπ™°πšƒπšπ™Έπš‡.𝚌)>1
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>|πš…π™°π™»πš„π™΄πš‚|
Usage

A classical utilisation of the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš πš’πšπš‘_𝚌𝚘𝚜𝚝𝚜 constraint corresponds to the following assignment problem. We have a set of persons 𝒫 as well as a set of jobs π’₯ to perform. Each job requires a number of persons restricted to a specified interval. In addition each person p has to be assigned to one specific job taken from a subset π’₯ p of π’₯. There is a cost C pj associated with the fact that person p is assigned to job j. The previous problem is modelled with one single πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš πš’πšπš‘_𝚌𝚘𝚜𝚝𝚜 constraint where the persons and the jobs respectively correspond to the items of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ and πš…π™°π™»πš„π™΄πš‚ collection.

The πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš πš’πšπš‘_𝚌𝚘𝚜𝚝𝚜 constraint can also be used for modelling a conjunction πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(πš‡ 1 ,πš‡ 2 ,...,πš‡ πš— ) and Ξ± 1 Β·πš‡ 1 +Ξ± 2 Β·πš‡ 2 +...+Ξ± n Β·πš‡ πš— =π™²π™Ύπš‚πšƒ. For this purpose we set the domain of the πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ variables to {0,1} and the cost attribute 𝚌 of a variable πš‡ πš’ and one of its potential value πš“ to Ξ± i Β·πš“. In practice this can be used for the magic squares and the magic hexagon problems where all the Ξ± i are set to 1.

Algorithm

[Regin99a], [Regin02]

Reformulation

Let n and m respectively denote the number of items of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ and of the πš…π™°π™»πš„π™΄πš‚ collections. Let v 1 ,v 2 ,...,v m denote the values πš…π™°π™»πš„π™΄πš‚[1].πšŸπšŠπš•,πš…π™°π™»πš„π™΄πš‚[2].πšŸπšŠπš•,...,πš…π™°π™»πš„π™΄πš‚[m].πšŸπšŠπš•. In addition let 𝐿𝐼𝑁𝐸 i (1≀i≀n) denote the values βŒ©π™Όπ™°πšƒπšπ™Έπš‡[mΒ·(i-1)+1].𝚌,π™Όπ™°πšƒπšπ™Έπš‡[mΒ·(i-1)+2].𝚌,...,π™Όπ™°πšƒπšπ™Έπš‡[mΒ·i].𝚌βŒͺ, i.e.,Β the i-th line of the matrix π™Όπ™°πšƒπšπ™Έπš‡.

By introducing 2Β·n auxiliary variables U 1 ,U 2 ,...,U n and C 1 ,C 2 ,...,C n , the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš πš’πšπš‘_𝚌𝚘𝚜𝚝𝚜(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚,π™Όπ™°πšƒπšπ™Έπš‡,π™²π™Ύπš‚πšƒ) constraint can be expressed in term of the conjunction of one πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚) constraint, 2Β·n πšŽπš•πšŽπš–πšŽπš—πš constraints and one arithmetic constraint πšœπšžπš–_πšŒπšπš›.

For each variable V i (1≀i≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|) of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection a first πšŽπš•πšŽπš–πšŽπš—πš(U i ,〈v 1 ,v 2 ,...,v m βŒͺ,V i ) constraint provides the correspondence between the variable V i and the index of the value U i to which it is assigned. A second πšŽπš•πšŽπš–πšŽπš—πš(U i ,𝐿𝐼𝑁𝐸 i ,C i ) links the previous index U i to the cost C i variable associated with variable V i . Finally the total cost π™²π™Ύπš‚πšƒ is equal to the sum C 1 +C 2 +...+C n .

In the context of the Example slot we get the following conjunction of constraints:

Β Β Β πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’(〈3,3,3,6βŒͺ,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β βŒ©πšŸπšŠπš•-3 πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-3,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β πšŸπšŠπš•-5 πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-0,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β πšŸπšŠπš•-6 πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-1βŒͺ),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(1,〈3,5,6βŒͺ,3),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(1,〈3,5,6βŒͺ,3),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(1,〈3,5,6βŒͺ,3),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(3,〈3,5,6βŒͺ,6),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(1,〈4,1,7βŒͺ,4),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(1,〈1,0,8βŒͺ,1),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(1,〈3,2,1βŒͺ,3),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(3,〈0,0,6βŒͺ,6),

Β Β Β 14=4+1+3+6.

Systems

global_cardinality in SICStus.

See also

attached to cost variant: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (𝚌𝚘𝚜𝚝 associated with each πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ,πšŸπšŠπš•πšžπšŽ pair removed).

common keyword: πš–πš’πš—πš’πš–πšžπš–_πš πšŽπš’πšπš‘πš_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (cost filtering constraint,weighted assignment), πšœπšžπš–_𝚘𝚏_πš πšŽπš’πšπš‘πšπšœ_𝚘𝚏_πšπš’πšœπšπš’πš—πšŒπš_πšŸπšŠπš•πšžπšŽπšœ, πš πšŽπš’πšπš‘πšπšŽπš_πš™πšŠπš›πšπš’πšŠπš•_πšŠπš•πš•πšπš’πšπšΒ (weighted assignment).

implies: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’.

Keywords

application area: assignment.

filtering: cost filtering constraint.

modelling: cost matrix, scalar product.

problems: weighted assignment.

puzzles: magic square, magic hexagon.

For all items of πš…π™°π™»πš„π™΄πš‚:

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•
Graph property(ies)
𝐍𝐕𝐄𝐑𝐓𝐄𝐗=πš…π™°π™»πš„π™΄πš‚.πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ πš…π™°π™»πš„π™΄πš‚

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ,πšŸπšŠπš•πšžπšŽπšœ)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πšŸπšŠπš•πšžπšŽπšœ.πšŸπšŠπš•
Graph property(ies)
π’π”πŒ_π–π„πˆπ†π‡π“_π€π‘π‚π™Όπ™°πšƒπšπ™Έπš‡[(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πš”πšŽπš’-1)*|πš…π™°π™»πš„π™΄πš‚|+πšŸπšŠπš•πšžπšŽπšœ.πš”πšŽπš’].𝚌=π™²π™Ύπš‚πšƒ

Graph model

The first graph constraint enforces each value of the πš…π™°π™»πš„π™΄πš‚ collection to be taken by a specific number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. It is identical to the graph constraint used in the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint. The second graph constraint expresses the fact that the π™²π™Ύπš‚πšƒ variable is equal to the sum of the elementary costs associated with each variable -value assignment. All these elementary costs are recorded in the π™Όπ™°πšƒπšπ™Έπš‡ collection. More precisely, the cost c ij is recorded in the attribute 𝚌 of the ((i-1)Β·|πš…π™°π™»πš„π™΄πš‚)|+j) th entry of the π™Όπ™°πšƒπšπ™Έπš‡ collection. This is ensured by the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš restriction that enforces the fact that the items of the π™Όπ™°πšƒπšπ™Έπš‡ collection are sorted in lexicographically increasing order according to attributes πš’ and πš“.

PartsΒ (A) andΒ (B) of FigureΒ 5.142.1 respectively show the initial and final graph associated with the second graph constraint of the Example slot.

Figure 5.142.1. Initial and final graph of the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš πš’πšπš‘_𝚌𝚘𝚜𝚝𝚜 constraint
ctrs/global_cardinality_with_costsActrs/global_cardinality_with_costsB
(a) (b)