### 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},\cdots ,{c}_{n}$, where each elementary cost ${c}_{i}$ $\left(1\le i\le n\right)$ 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 $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left({v}_{i},〈{c}_{i,1},{c}_{i,2},\cdots ,{c}_{i,m}〉,{c}_{i}\right)$ 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 ${\sigma }_{1},{\sigma }_{2},\cdots ,{\sigma }_{m}$ of $1,2,\cdots ,m$ such that ${c}_{i,{\sigma }_{1}}\le {c}_{i,{\sigma }_{2}}\le \cdots \le {c}_{i,{\sigma }_{m}}$. Note that such permutation can be obtained by sorting the costs ${c}_{i,1},{c}_{i,2},\cdots ,{c}_{i,m}$ by increasing order and by collecting the position ${\sigma }_{j}$ where item ${c}_{i,j}$ is located in the sorted list. Assuming that we perform arc-consistency on the $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$, we now describe three different ways to obtain the effect we want to achieve:

• A first direct way is to use a built in facility that, given variable ${v}_{i}$ and the corresponding list of values ${\sigma }_{1},{\sigma }_{2},\cdots ,{\sigma }_{m}$ introduced before, creates a choice point and tries to successively assign values ${\sigma }_{1},{\sigma }_{2},\cdots ,{\sigma }_{m}$ to ${v}_{i}$. Note that, once ${v}_{i}$ is fixed there is no need to enumerate on the corresponding elementary cost variable ${c}_{i}$ since, by propagation, $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left({v}_{i},〈{c}_{i,1},{c}_{i,2},\cdots ,{c}_{i,m}〉,{c}_{i}\right)$ will fix ${c}_{i}$. Consequently the cost variables do not need to be passed to the search procedure.

• A second indirect way, used when we want to only rely on a standard built in that creates a choice point and tries to assign values to a variable in increasing value order, is to introduce an extra variable ${u}_{i}$. The idea is to link variable ${u}_{i}$ to variable ${v}_{i}$ in such a way that, when we try to assign values in increasing value order to variable ${u}_{i}$, both variables ${v}_{i}$ and ${c}_{i}$ get fixed and, in addition, values of ${c}_{i}$ are increasing. This can be modelled by introducing the following two $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraints:

1. $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left({u}_{i},〈{\sigma }_{1},{\sigma }_{2},\cdots ,{\sigma }_{m}〉,{v}_{i}\right)$

2. $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left({v}_{i},〈{c}_{i,1},{c}_{i,2},\cdots ,{c}_{i,m}〉,{c}_{i}\right)$

The effect of a dedicated built in that tries to assign values to a variable according to an explicit list of values is achieved by introducing the first $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraint. Again, once ${u}_{i}$ is fixed the first $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraint will fix variable ${v}_{i}$. Then the second $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraint will also fix variable ${c}_{i}$. Consequently, both the cost and the decision variables do not need to be passed to the search procedure, i.e., we just need to pass the newly introduced variables ${u}_{i}$.

• Finally, we can first label on the cost variable ${c}_{i}$ in increasing value order. If the costs ${c}_{i,1},{c}_{i,2},\cdots ,{c}_{i,m}$ are all distinct then the $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left({v}_{i},〈{c}_{i,1},{c}_{i,2},\cdots ,{c}_{i,m}〉,{c}_{i}\right)$ constraint will fix ${v}_{i}$ by propagation since we assume $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ to perform arc-consistency. Otherwise, when the costs ${c}_{i,1},{c}_{i,2},\cdots ,{c}_{i,m}$ are not all distinct, we also need to label the decision variable ${v}_{i}$.

##### Figure 3.7.35. Given a decision variable $v$ and a corresponding cost variable $c$ linked by the $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left(v,〈5,6,2,9,9〉,c\right)$ 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 $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left(u,〈3,1,2,4,5〉,v\right)$ 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$\left(\mathrm{𝑣𝑎𝑟},\mathrm{𝑙𝑖𝑠𝑡}_\mathrm{𝑣𝑎𝑙𝑢𝑒𝑠}\right)$ creates a choice point and tries to successively assign variable $\mathrm{𝑣𝑎𝑟}$ an integer value from the list $\mathrm{𝑙𝑖𝑠𝑡}_\mathrm{𝑣𝑎𝑙𝑢𝑒𝑠}$ with respect to their ordering. The primitive indomain$\left(\mathrm{𝑣𝑎𝑟}\right)$ also creates a choice point and tries to successively assign variable $\mathrm{𝑣𝑎𝑟}$ an integer value of its domain, by increasing value order.