Inequality-sum : a global constraint capturing the objective function
RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 2, pp. 123-139.

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.

DOI : 10.1051/ro:2005007
Classification : 65K05, 90C35 
@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 = {https://www.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  - https://www.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 https://www.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, Tome 39 (2005) no. 2, pp. 123-139. doi : 10.1051/ro:2005007. https://www.numdam.org/articles/10.1051/ro:2005007/

[1] R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows. Prentice Hall (1993). | MR

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

[3] J. Blazewicz, K. Ecker, G. Schmidt and J. Weglarz, Scheduling in Computer and Manufacturing Systems. Springer-Verlag (1993). | Zbl

[4] 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. | Zbl

[5] R. Dechter, I. Meiri and J. Pearl, Temporal constraint networks. Artif. Intell. 49 (1991) 61-95. | Zbl

[6] M. Dror, W. Kubiak and P. Dell'Olmo, Scheduling chains to minimize mean flow time. Inform. Process. Lett. 61 (1997) 297-301.

[7] 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.

[8] 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. | Zbl

[9] 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. | Zbl

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

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

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

[13] 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.

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

[15] P. Van Hentenryck, Y. Deville and C.-M. Teng, A generic arc-consistency algorithm and its specializations. Artif. Intell. 57 (October 1992) 291-321. | Zbl

  • Pelleau, Marie; Truchet, Charlotte; Benhamou, Frédéric The octagon abstract domain for continuous constraints, Constraints, Volume 19 (2014) no. 3, p. 309 | DOI:10.1007/s10601-014-9162-x
  • Dao, Thi-Bich-Hanh; Duong, Khanh-Chuong; Vrain, Christel, 2013 IEEE 25th International Conference on Tools with Artificial Intelligence (2013), p. 1060 | DOI:10.1109/ictai.2013.158
  • Kovács, András; Beck, J. Christopher A global constraint for total weighted completion time for unary resources, Constraints, Volume 16 (2011) no. 1, p. 100 | DOI:10.1007/s10601-009-9088-x
  • Pelleau, Marie; Truchet, Charlotte; Benhamou, Frédéric Octagonal Domains for Continuous Constraints, Principles and Practice of Constraint Programming – CP 2011, Volume 6876 (2011), p. 706 | DOI:10.1007/978-3-642-23786-7_53
  • Petit, Thierry; Régin, Jean-Charles; Beldiceanu, Nicolas A Θ(n) Bound-Consistency Algorithm for the Increasing Sum Constraint, Principles and Practice of Constraint Programming – CP 2011, Volume 6876 (2011), p. 721 | DOI:10.1007/978-3-642-23786-7_54
  • Kovács, András; Beck, J. Christopher A global constraint for total weighted completion time for cumulative resources, Engineering Applications of Artificial Intelligence, Volume 21 (2008) no. 5, p. 691 | DOI:10.1016/j.engappai.2008.03.004

Cité par 6 documents. Sources : Crossref