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Β [Freuder82]. 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 [1,V]. 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., πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ 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.
ctrs/preface-174-tikz

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 πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ 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 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 πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ 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 [1,V]) 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.