5.221. minimum_weight_alldifferent

DESCRIPTIONLINKSGRAPH
Origin

[FocacciLodiMilano99]

Constraint

πš–πš’πš—πš’πš–πšžπš–_πš πšŽπš’πšπš‘πš_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™Όπ™°πšƒπšπ™Έπš‡,π™²π™Ύπš‚πšƒ)

Synonyms

πš–πš’πš—πš’πš–πšžπš–_πš πšŽπš’πšπš‘πš_πšŠπš•πš•πšπš’πšπš, πš–πš’πš—πš’πš–πšžπš–_πš πšŽπš’πšπš‘πš_πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš, πš–πš’πš—_πš πšŽπš’πšπš‘πš_πšŠπš•πš•πšπš’πšπš, πš–πš’πš—_πš πšŽπš’πšπš‘πš_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πš–πš’πš—_πš πšŽπš’πšπš‘πš_πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš.

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

All variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection should take a distinct value located within interval [1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|]. In addition π™²π™Ύπš‚πšƒ is equal to the sum of the costs associated with the fact that we assign value i to variable j. These costs are given by the matrix π™Όπ™°πšƒπšπ™Έπš‡.

Example
2,3,1,4,πš’-1πš“-1𝚌-4,πš’-1πš“-2𝚌-1,πš’-1πš“-3𝚌-7,πš’-1πš“-4𝚌-0,πš’-2πš“-1𝚌-1,πš’-2πš“-2𝚌-0,πš’-2πš“-3𝚌-8,πš’-2πš“-4𝚌-2,πš’-3πš“-1𝚌-3,πš’-3πš“-2𝚌-2,πš’-3πš“-3𝚌-1,πš’-3πš“-4𝚌-6,πš’-4πš“-1𝚌-0,πš’-4πš“-2𝚌-0,πš’-4πš“-3𝚌-6,πš’-4πš“-4𝚌-5,17

The πš–πš’πš—πš’πš–πšžπš–_πš πšŽπš’πšπš‘πš_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint holds since the cost 17 corresponds to the sum π™Όπ™°πšƒπšπ™Έπš‡[(1-1)Β·4+2].𝚌+π™Όπ™°πšƒπšπ™Έπš‡[(2-1)Β·4+3].𝚌+π™Όπ™°πšƒπšπ™Έπš‡[(3-1)Β·4+1].𝚌+π™Όπ™°πšƒπšπ™Έπš‡[(4-1)Β·4+4].𝚌=π™Όπ™°πšƒπšπ™Έπš‡[2].𝚌+π™Όπ™°πšƒπšπ™Έπš‡[7].𝚌+π™Όπ™°πšƒπšπ™Έπš‡[9].𝚌+π™Όπ™°πšƒπšπ™Έπš‡[16].𝚌=1+8+3+5.

Algorithm

The Hungarian method for the assignment problemΒ [Kuhn55] can be used for evaluating the bounds of the π™²π™Ύπš‚πšƒ variable. A filtering algorithm is described inΒ [Sellmann02]. It can be used for handling both side of the πš–πš’πš—πš’πš–πšžπš–_πš πšŽπš’πšπš‘πš_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint:

  • Evaluating a lower bound of the π™²π™Ύπš‚πšƒ variable and pruning the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection in order to not exceed the maximum value of π™²π™Ύπš‚πšƒ.

  • Evaluating an upper bound of the π™²π™Ύπš‚πšƒ variable and pruning the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection in order to not be under the minimum value of π™²π™Ύπš‚πšƒ.

Systems

assignment in SICStus.

See also

attached to cost variant: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

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

Keywords

application area: assignment.

characteristic of a constraint: core.

filtering: cost filtering constraint, Hungarian method for the assignment problem.

final graph structure: one_succ.

modelling: cost matrix.

problems: weighted assignment.

Arc input(s)

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

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πš”πšŽπš’
Graph property(ies)
β€’ 𝐍𝐓𝐑𝐄𝐄=0
β€’ π’π”πŒ_π–π„πˆπ†π‡π“_π€π‘π‚π™Όπ™°πšƒπšπ™Έπš‡βˆ‘(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πš”πšŽπš’-1)*|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›.𝚌=π™²π™Ύπš‚πšƒ

Graph model

Since each variable takes one value, and because of the arc constraint πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πš”πšŽπš’, each vertex of the initial graph belongs to the final graph and has exactly one successor. Therefore the sum of the out-degrees of the vertices of the final graph is equal to the number of vertices of the final graph. Since the sum of the in-degrees is equal to the sum of the out-degrees, it is also equal to the number of vertices of the final graph. Since 𝐍𝐓𝐑𝐄𝐄=0, each vertex of the final graph belongs to a circuit. Therefore each vertex of the final graph has at least one predecessor. Since we saw that the sum of the in-degrees is equal to the number of vertices of the final graph, each vertex of the final graph has exactly one predecessor. We conclude that the final graph consists of a set of vertex-disjoint elementary circuits.

Finally the 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 πš“.

Figure 5.221.1. Initial and final graph of the πš–πš’πš—πš’πš–πšžπš–_πš πšŽπš’πšπš‘πš_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint
ctrs/minimum_weight_alldifferentActrs/minimum_weight_alldifferentB
(a) (b)

PartsΒ (A) andΒ (B) of FigureΒ 5.221.1 respectively show the initial and final graph associated with the Example slot. Since we use the π’π”πŒ_π–π„πˆπ†π‡π“_𝐀𝐑𝐂 graph property, the arcs of the final graph are stressed in bold. We also indicate their corresponding weight.