Volume 39, Number 2, April-June 2005
|Page(s)||123 - 139|
|Published online||15 October 2005|
Inequality-sum: a global constraint capturing the objective function
Les Taissounieres HB2
1681, route des Dolines Sophia-Antipolis,
06560 Valbonne, France; firstname.lastname@example.org
2 Université de Nice–Sophia-Antipolis, Projet COPRIN I3S/CNRS-INRIA-CERMICS, ESSI, 930, route des Colles, B.P. 145, 06903 Sophia-Antipolis, France; email@example.com
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 = ∑xi, and where the integer variables xi are subject to difference constraints of the form xj - xi ≤ 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 xi 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.
Mathematics Subject Classification: 65K05 / 90C35
© EDP Sciences, 2005
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.