3.7.113. Heuristics and Berge-acyclic constraint network
Consider a conjunction of constraints such that:
The constraint network corresponding to the conjunction is not Berge-acyclic.
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 in needed any more to check that their is a solution, provided we achieve arc -consistency on the remaining constraints. This stems from [DechterPearl88], which itself is a consequence of [Freuder82]. This can be achieved by fixing the variables in such a way that some constraints get entailed even if they still mention some variables that are not yet fixed. Let us illustrate that idea on a matrix model where we have a matrix of domain variables taking a value in interval . Assume that:
On each row of we have a constraint that can be described in term of a counter -free automaton.
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 column constraints (i.e., constraints) get entailed. If this is the case the remaining constraint network consists of rows constraints and of one single column constraint.
Figure 3.7.26. (A,C): Initial constraint network for a by matrix (with column constraints , , , and row constraints , , ) and corresponding intersection graph; (B,D): Berge -acyclic constraint network after the entailment of the column constraints , and and corresponding cycle -free intersection graph.
As illustrated by Figure 3.7.26, 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 constraint that only restricts the minimum number of occurrences of certain values so that it becomes entailed. As an example, let us consider a constraint involving 10 variables that enforce 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 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 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 ) 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 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.