Bound-consistent spread constraint

Schaus, Pierre [UCL] Régin, Jean-Charles [Université de Nice-Sophia antipolis]

Given a vector of finite domain variables, the spread constraint aims at minimizing the sum of squares of these variables while constraining the sum of these to be equal to a given value. We improve the existing filtering for spread achieving a bound-consistent filtering without increasing the complexity. Previous versions of the algorithm considered a relaxed version of the bound-consistency assuming interval domains defined on rational numbers rather than integers. We apply our new algorithm to a real-life problem: the daily assignment of newborn infant patients to nurses in a hospital. The objective is to balance the workload of the nurses, while satisfying a variety of side constraints. Prior work proposed a MIP model for this problem, which unfortunately did not scale to large instances and only approximated the objective function, since minimizing the variance cannot be expressed in a linear model. This paper presents a two-step approach, first assigning nurses to region of the hospital then assigning the patients to these nurses. We show that our approach allows to tackle large instances with hundreds of patients and nurses in a few seconds using the OscaR optimization system.