### 3.7.118. Heuristics and Berge-acyclic constraint network

Consider a conjunction $𝒞$ of constraints such that:

1. The constraint network $𝒩$ corresponding to the conjunction $𝒞$ is not Berge-acyclic.

2. The filtering algorithms associated with the different constraints of the conjunction $𝒞$ all achieve arc-consistency.

In this context, one can design a heuristics that fix enough variables, but not all, so that the remaining constraint network $𝒩$ becomes Berge-acyclic.The point is that, as soon as the constraint network becomes Berge-acyclic no search is needed any more to check that there is a solution, provided we achieve arc-consistency on the remaining constraints. This stems from [DechterPearl88], which itself is a consequence of This can be achieved by fixing the variables in such a way that some constraints get entailed even though they still mention some variables that are not yet fixed. Let us illustrate that idea on a matrix model where we have a $R×K$ matrix $ℳ$ of domain variables taking a value in interval $\left[1,V\right]$. Assume that:

Note that arc-consistency can be achieved for such constraints. For this constraint pattern, an assignment strategy that systematically tries creating a Berge-acyclic constraint network can be achieved as follows. Fix some variables so that $K-1$ column constraints (i.e., $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraints) get entailed. If this is the case the remaining constraint network consists of $R$ rows constraints and of a single column constraint.

##### Figure 3.7.34. (A) Initial constraint network for a $R=3$ by $K=4$ matrix (with column constraints ${C}_{1}$, ${C}_{2}$, ${C}_{3}$, ${C}_{4}$ and row constraints ${C}_{5}$, ${C}_{6}$, ${C}_{7}$) and (B) corresponding intersection graph; (C) Berge-acyclic constraint network after the entailment of the column constraints ${C}_{2}$, ${C}_{3}$ and ${C}_{4}$ and (D) corresponding cycle-free intersection graph. As illustrated by Figure 3.7.34, this typically corresponds to a Berge-acyclic constraint network. Let us now finally explain how to assign values to a subset of variables of a $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraint that only restricts the minimum number of occurrences of certain values so that it becomes entailed. As an example, let us consider a $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraint involving 10 variables which forces at least three occurrences of value 1 and one occurrence of value 2. A heuristics needs only fixing 4 variables out of the 10 variables to values 1, 1, 1 and 2 so that the corresponding $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ gets entailed. A typical instance of this pattern corresponds to nurse scheduling problems where:

• Each row of $ℳ$ corresponds to the timetable of a person over $K$ consecutive days. Using a counter free automaton the corresponding row constraint encodes all legal rules of a valid schedule.

• Each column of $ℳ$ describes the request for a minimum number of services on a given day. Types of work (i.e., values in $\left[1,V\right]$) can for instance be interpreted as a morning shift, an afternoon shift, a night shift or a day off.

The heuristics first addresses the coverage constraints only (i.e., the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraints). It seeks to assign enough nurses to given shifts on given day to satisfy all but one coverage constraints. Once this is done, the remaining variables can be labelled without search.