# Inequality-sum: a global constraint capturing the objective function

Jean-Charles Régin; Michel Rueher

RAIRO - Operations Research (2010)

- Volume: 39, Issue: 2, page 123-139
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topRégin, Jean-Charles, and Rueher, Michel. "Inequality-sum: a global constraint capturing the objective function." RAIRO - Operations Research 39.2 (2010): 123-139. <http://eudml.org/doc/105325>.

@article{Régin2010,

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 = ∑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.
},

author = {Régin, Jean-Charles, Rueher, Michel},

journal = {RAIRO - Operations Research},

language = {eng},

month = {3},

number = {2},

pages = {123-139},

publisher = {EDP Sciences},

title = {Inequality-sum: a global constraint capturing the objective function},

url = {http://eudml.org/doc/105325},

volume = {39},

year = {2010},

}

TY - JOUR

AU - Régin, Jean-Charles

AU - Rueher, Michel

TI - Inequality-sum: a global constraint capturing the objective function

JO - RAIRO - Operations Research

DA - 2010/3//

PB - EDP Sciences

VL - 39

IS - 2

SP - 123

EP - 139

AB -
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.

LA - eng

UR - http://eudml.org/doc/105325

ER -

## References

top- R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows. Prentice Hall (1993).
- N. Beldiceanu and E. Contejean, Introducing global constraints in chip. J. Math. Comput. Model.20 (1994) 97–123.
- J. Blazewicz, K. Ecker, G. Schmidt and J. Weglarz, Scheduling in Computer and Manufacturing Systems. Springer-Verlag (1993).
- J. Carlier and E. Pinson, A practical use of jackson's preemptive schedule for solving the job-shop problem. Ann. Oper. Res.26 (1990) 269–287.
- R. Dechter, I. Meiri and J. Pearl, Temporal constraint networks. Artif. Intell.49 (1991) 61–95.
- M. Dror, W. Kubiak and P. Dell'Olmo, Scheduling chains to minimize mean flow time. Inform. Process. Lett.61 (1997) 297–301.
- P. Van Hentenryck and Y. Deville, The cardinality operator: A new logical connective for constraint logic programming, in Proc. of ICLP'91 (1991) 745–759.
- P. Van Hentenryck, V. Saraswat and Y. Deville, Design, implementation, and evaluation of the constraint language cc(FD). J. Logic Program.37 (1998) 139–164.
- M. Rueher and J.-C. Régin, 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.
- C.E. Leiserson and J.B. Saxe, A mixed-integer linear programming problem which is efficiently solvable. J. Algorithms9 (1988) 114–128.
- J.-C. Régin, A filtering algorithm for constraints of difference in CSPs, in Proc. of AAAI-94. Seattle, Washington (1994) 362–367.
- J.-C. Régin, Generalized arc consistency for global cardinality constraint, in Proc. of AAAI-96, Portland, Oregon (1996) 209–215.
- H. Simonis, 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.
- R.E. Tarjan, Data Structures and Network Algorithms. CBMS 44 SIAM (1983).
- P. Van Hentenryck, Y. Deville and C.-M. Teng, A generic arc-consistency algorithm and its specializations. Artif. Intell.57 (October 1992) 291–321.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.