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.

@article{RO_2005__39_2_123_0, author = {R\'egin, Jean-Charles and Rueher, Michel}, title = {Inequality-sum : a global constraint capturing the objective function}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {123--139}, publisher = {EDP-Sciences}, volume = {39}, number = {2}, year = {2005}, doi = {10.1051/ro:2005007}, mrnumber = {2181795}, zbl = {1104.90051}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro:2005007/} }

TY - JOUR AU - Régin, Jean-Charles AU - Rueher, Michel TI - Inequality-sum : a global constraint capturing the objective function JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2005 SP - 123 EP - 139 VL - 39 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro:2005007/ DO - 10.1051/ro:2005007 LA - en ID - RO_2005__39_2_123_0 ER -

%0 Journal Article %A Régin, Jean-Charles %A Rueher, Michel %T Inequality-sum : a global constraint capturing the objective function %J RAIRO - Operations Research - Recherche Opérationnelle %D 2005 %P 123-139 %V 39 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro:2005007/ %R 10.1051/ro:2005007 %G en %F RO_2005__39_2_123_0

Régin, Jean-Charles; Rueher, Michel. Inequality-sum : a global constraint capturing the objective function. RAIRO - Operations Research - Recherche Opérationnelle, Volume 39 (2005) no. 2, pp. 123-139. doi : 10.1051/ro:2005007. http://archive.numdam.org/articles/10.1051/ro:2005007/

[1] Network Flows. Prentice Hall (1993). | MR

, and ,[2] Introducing global constraints in chip. J. Math. Comput. Model. 20 (1994) 97-123. | Zbl

and ,[3] Scheduling in Computer and Manufacturing Systems. Springer-Verlag (1993). | Zbl

, , and ,[4] A practical use of jackson's preemptive schedule for solving the job-shop problem. Ann. Oper. Res. 26 (1990) 269-287. | Zbl

and ,[5] Temporal constraint networks. Artif. Intell. 49 (1991) 61-95. | Zbl

, and ,[6] Scheduling chains to minimize mean flow time. Inform. Process. Lett. 61 (1997) 297-301.

, and ,[7] The cardinality operator: A new logical connective for constraint logic programming, in Proc. of ICLP'91 (1991) 745-759.

and ,[8] Design, implementation, and evaluation of the constraint language cc(FD). J. Logic Program. 37 (1998) 139-164. | Zbl

, and ,[9] A global constraint combining a sum constraint and difference constraints, in Proc. of CP'2000, Sixth International Conference on Principles and Practice of Constraint Programming. Singapore, Springer-Verlag. Lect. Notes Comput. Sci. 1894 (2000) 384-395. | Zbl

and ,[10] A mixed-integer linear programming problem which is efficiently solvable. J. Algorithms 9 (1988) 114-128. | Zbl

and ,[11] A filtering algorithm for constraints of difference in CSPs, in Proc. of AAAI-94. Seattle, Washington (1994) 362-367.

,[12] Generalized arc consistency for global cardinality constraint, in Proc. of AAAI-96, Portland, Oregon (1996) 209-215.

,[13] Problem classification scheme for finite domain constraint solving, in CP96, Workshop on Constraint Programming Applications: An Inventory and Taxonomy, Cambridge, MA, USA (1996) 1-26.

,[14] Data Structures and Network Algorithms. CBMS 44 SIAM (1983). | MR | Zbl

,[15] A generic arc-consistency algorithm and its specializations. Artif. Intell. 57 (October 1992) 291-321. | Zbl

, and ,*Cited by Sources: *