Inequality-sum: a global constraint capturing the objective function

¹ ILOG Les Taissounieres HB2 1681, route des Dolines Sophia-Antipolis, 06560 Valbonne, France; regin@ilog.fr
² Université de Nice–Sophia-Antipolis, Projet COPRIN I3S/CNRS-INRIA-CERMICS, ESSI, 930, route des Colles, B.P. 145, 06903 Sophia-Antipolis, France; rueher@essi.fr

Received: 16 March 2004

Abstract

This paper introduces a new method to prune the domains of the variables in constrained optimization problems where the objective function is defined by a sum y = ∑x_i, and where the integer variables x_i are subject to difference constraints of the form x_j - x_i ≤ c. An important application area where such problems occur is deterministic scheduling with the mean flow time as optimality criteria. This new constraint is also more general than a sum constraint defined on a set of ordered variables. Classical approaches perform a local consistency filtering after each reduction of the bound of y. The drawback of these approaches comes from the fact that the constraints are handled independently. We introduce here a global constraint that enables to tackle simultaneously the whole constraint system, and thus, yields a more effective pruning of the domains of the x_i when the bounds of y are reduced. An efficient algorithm, derived from Dijkstra's shortest path algorithm, is introduced to achieve interval consistency on this global constraint.