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.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.