Inequality-sum : a global constraint capturing the objective function

Régin, Jean-Charles  ; Rueher, Michel 

RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 2, pp. 123-139

Résumé

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=\Sigma x_i$, and where the integer variables $x_i$ are subject to difference constraints of the form $x_j-x_i\le 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.

Détail

DOI : 10.1051/ro:2005007

Classification : 65K05, 90C35