Inequality-sum : a global constraint capturing the objective function

Jean-Charles Régin; Michel Rueher

RAIRO - Operations Research - Recherche Opérationnelle (2005)

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

Abstract

top
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 = Σ x i , and where the integer variables x i are subject to difference constraints of the form x j - x i ≤ 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.

How to cite

top

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

@article{Régin2005,
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=\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.},
author = {Régin, Jean-Charles, Rueher, Michel},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
language = {eng},
number = {2},
pages = {123-139},
publisher = {EDP-Sciences},
title = {Inequality-sum : a global constraint capturing the objective function},
url = {http://eudml.org/doc/245189},
volume = {39},
year = {2005},
}

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
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=\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.
LA - eng
UR - http://eudml.org/doc/245189
ER -

References

top
  1. [1] R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows. Prentice Hall (1993). MR1205775
  2. [2] N. Beldiceanu and E. Contejean, Introducing global constraints in chip. J. Math. Comput. Model. 20 (1994) 97–123. Zbl0816.68048
  3. [3] J. Blazewicz, K. Ecker, G. Schmidt and J. Weglarz, Scheduling in Computer and Manufacturing Systems. Springer-Verlag (1993). Zbl0767.90033
  4. [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. Zbl0709.90061
  5. [5] R. Dechter, I. Meiri and J. Pearl, Temporal constraint networks. Artif. Intell. 49 (1991) 61–95. Zbl0737.68070
  6. [6] M. Dror, W. Kubiak and P. Dell’Olmo, Scheduling chains to minimize mean flow time. Inform. Process. Lett. 61 (1997) 297–301. 
  7. [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. [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. Zbl0920.68026
  9. [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. Zbl1044.68794
  10. [10] C.E. Leiserson and J.B. Saxe, A mixed-integer linear programming problem which is efficiently solvable. J. Algorithms 9 (1988) 114–128. Zbl0649.90077
  11. [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. [12] J.-C. Régin, Generalized arc consistency for global cardinality constraint, in Proc. of AAAI-96, Portland, Oregon (1996) 209–215. 
  13. [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. [14] R.E. Tarjan, Data Structures and Network Algorithms. CBMS 44 SIAM (1983). Zbl0584.68077MR826534
  15. [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. Zbl0763.68059

NotesEmbed ?

top

You must be logged in to post comments.