### 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},\beta ―,{c}_{n}$, where each elementary cost ${c}_{i}$ $\left(1\beta €i\beta €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{\pi \pi \pi \pi \pi \pi \pi }$$\left({v}_{i},\beta ©{c}_{i,1},{c}_{i,2},\beta ―,{c}_{i,m}\beta ͺ,{c}_{i}\right)$ stating that ${c}_{i}=j\beta {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 ${\mathrm{Ο}}_{1},{\mathrm{Ο}}_{2},\beta ―,{\mathrm{Ο}}_{m}$ of $1,2,\beta ―,m$ such that ${c}_{i,{\mathrm{Ο}}_{1}}\beta €{c}_{i,{\mathrm{Ο}}_{2}}\beta €\beta ―\beta €{c}_{i,{\mathrm{Ο}}_{m}}$. Note that such permutation can be obtained by sorting the costs ${c}_{i,1},{c}_{i,2},\beta ―,{c}_{i,m}$ by increasing order and by collecting the position ${\mathrm{Ο}}_{j}$ where item ${c}_{i,j}$ is located in the sorted list. Assuming that we perform arc-consistency on the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$, we now describe three different ways to obtain the effect we want to achieve:

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 $\mathrm{\pi £\pi \pi }$ an integer value from the list with respect to their ordering. The primitive indomain$\left(\mathrm{\pi £\pi \pi }\right)$ also creates a choice point and tries to successively assign variable $\mathrm{\pi £\pi \pi }$ an integer value of its domain, by increasing value order.