3.7.132. Labelling by increasing cost

Some optimisation problems involve minimising a cost c consisting of a sum of elementary costs c 1 ,c 2 ,β‹―,c n , where each elementary cost c i (1≀i≀n) is directly linked to the value assigned to a decision variable v i . Without loss of generality we assume that each decision variable will be assigned a value between 1 and m. The link between a decision variable v i and its corresponding cost c i is usually expressed by a constraint of the form πšŽπš•πšŽπš–πšŽπš—πš(v i ,〈c i,1 ,c i,2 ,β‹―,c i,m βŒͺ,c i ) stating that c i =jβ‡’c i =c i,j . During search, while enumerating on the different values of a decision variable v i , we would like to try out values of v i so that the corresponding cost c i increases. This means we want to use a permutation Οƒ 1 ,Οƒ 2 ,β‹―,Οƒ m of 1,2,β‹―,m such that c i,Οƒ 1 ≀c i,Οƒ 2 ≀⋯≀c i,Οƒ m . Note that such permutation can be obtained by sorting the costs c i,1 ,c i,2 ,β‹―,c i,m by increasing order and by collecting the position Οƒ j where item c i,j is located in the sorted list. Assuming that we perform arc-consistency on the πšŽπš•πšŽπš–πšŽπš—πš, we now describe three different ways to obtain the effect we want to achieve:

Figure 3.7.35. Given a decision variable v and a corresponding cost variable c linked by the πšŽπš•πšŽπš–πšŽπš—πš(v,〈5,6,2,9,9βŒͺ,c) constraint, illustration of three ways for labelling by increasing cost: partΒ (A) labels directly on the decision variable v using an appropriate order so that successive values of c are increasing; partΒ (B) introduces a variable u linked to v by the πšŽπš•πšŽπš–πšŽπš—πš(u,〈3,1,2,4,5βŒͺ,v) constraint and labels on u by increasing value order; partΒ (C) labels first on the cost variable c by increasing value order, and then on variable v.

FigureΒ 3.7.35 illustrates the three ways of labelling previously introduced. The primitive member(π‘£π‘Žπ‘Ÿ,𝑙𝑖𝑠𝑑_π‘£π‘Žπ‘™π‘’π‘’π‘ ) creates a choice point and tries to successively assign variable π‘£π‘Žπ‘Ÿ an integer value from the list 𝑙𝑖𝑠𝑑_π‘£π‘Žπ‘™π‘’π‘’π‘  with respect to their ordering. The primitive indomain(π‘£π‘Žπ‘Ÿ) also creates a choice point and tries to successively assign variable π‘£π‘Žπ‘Ÿ an integer value of its domain, by increasing value order.