{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T03:44:34Z","timestamp":1777693474507,"version":"3.51.4"},"reference-count":68,"publisher":"Elsevier","isbn-type":[{"value":"9780444527264","type":"print"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1016\/s1574-6526(06)80010-6","type":"book-chapter","created":{"date-parts":[[2008,2,26]],"date-time":"2008-02-26T16:51:39Z","timestamp":1204044699000},"page":"169-208","source":"Crossref","is-referenced-by-count":53,"title":["Global Constraints"],"prefix":"10.1016","member":"78","reference":[{"issue":"7","key":"10.1016\/S1574-6526(06)80010-6_bib1","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0895-7177(93)90068-A","article-title":"Extending CHIP in order to solve complex scheduling and placement problems","volume":"17","author":"Aggoun","year":"1993","journal-title":"Journal of Mathematical and Computer Modelling"},{"key":"10.1016\/S1574-6526(06)80010-6_bib2","series-title":"Network Flows","author":"Ahuja","year":"1993"},{"key":"10.1016\/S1574-6526(06)80010-6_bib3","series-title":"Proceedings of the Eleventh International Conference on Principles and Practice of Constraint Programming (CP 2005)","first-page":"62","article-title":"Inter-distance Constraint: An Extension of the All-Different Constraint for Scheduling Equal Length Jobs","volume":"volume 3709","author":"Artiouchine","year":"2005"},{"issue":"1\u20134","key":"10.1016\/S1574-6526(06)80010-6_bib4","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1023\/A:1021805623454","article-title":"Dynamic Global Constraints in Backtracking Based Environments","volume":"118","author":"Bart\u00e1k","year":"2003","journal-title":"Annals of Operations Research"},{"key":"10.1016\/S1574-6526(06)80010-6_bib5","series-title":"Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming (CP 2004)","first-page":"107","article-title":"Deriving Filtering Algorithms from Constraint Checkers","volume":"volume 3258","author":"Beldiceanu","year":"2004"},{"key":"10.1016\/S1574-6526(06)80010-6_bib6","article-title":"Global constraint catalog","author":"Beldiceanu","year":"2005"},{"key":"10.1016\/S1574-6526(06)80010-6_bib7","series-title":"Proceedings of the Eleventh International Conference on Principles and Practice of Constraint Programming (CP 2005)","first-page":"92","article-title":"Graph invariants as necessary conditions for global constraints","volume":"volume 3709","author":"Beldiceanu","year":"2005"},{"key":"10.1016\/S1574-6526(06)80010-6_bib8","series-title":"Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming (CP 2004)","first-page":"138","article-title":"Disjoint, partition and intersection constraints for set and multiset variables","volume":"volume 3258","author":"Bessi\u00e8re","year":"2004"},{"key":"10.1016\/S1574-6526(06)80010-6_bib9","series-title":"Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming (CP 2004)","first-page":"716","article-title":"The tractability of global constraints","volume":"volume 3258","author":"Bessi\u00e8re","year":"2004"},{"key":"10.1016\/S1574-6526(06)80010-6_bib10","series-title":"Proceedings of the Twentieth","first-page":"60","article-title":"The range and roots constraints: Specifying counting and occurrence problems","author":"Bessi\u00e8re","year":"2005"},{"key":"10.1016\/S1574-6526(06)80010-6_bib11","doi-asserted-by":"crossref","DOI":"10.21236\/AD0249662","article-title":"A Procedure for Determining a Family of Minimum-Cost Network Flow Patterns","author":"Busacker","year":"1960"},{"key":"10.1016\/S1574-6526(06)80010-6_bib12","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1016\/0377-2217(94)90379-4","article-title":"Adjustment of heads and tails for the job-shop problem","volume":"78","author":"Carlier","year":"1994","journal-title":"Euro. J. Oper. Res."},{"key":"10.1016\/S1574-6526(06)80010-6_bib13","series-title":"Proceedings of Deductive and Object-Oriented Databases, Third International Conference (DOOD'93)","first-page":"67","article-title":"A Deductive and Object-Oriented Approach to a Complex Scheduling Problem","author":"Caseau","year":"1993"},{"key":"10.1016\/S1574-6526(06)80010-6_bib14","series-title":"Linear programming","author":"Chv\u00e1tal","year":"1983"},{"key":"10.1016\/S1574-6526(06)80010-6_bib15","series-title":"Activity Analysis of Production and Allocation \u2014 Proceedings of a conference","first-page":"339","article-title":"Maximization of a linear function of variables subject to linear inequalities","author":"Dantzig","year":"1951"},{"key":"10.1016\/S1574-6526(06)80010-6_bib16","series-title":"Proceedings of the Eleventh International Conference on Principles and Practice of Constraint Programming (CP 2005)","first-page":"211","article-title":"CP(Graph): Introducing a Graph Computation Domain in Constraint Programming","volume":"volume 3709","author":"Dooms","year":"2005"},{"key":"10.1016\/S1574-6526(06)80010-6_bib17","series-title":"Proceedings of the Fifth International Conference on Principles and Practice of Constraint Programming (CP 1999)","first-page":"189","article-title":"Cost-based domain filtering","volume":"volume 1713","author":"Focacci","year":"1999"},{"key":"10.1016\/S1574-6526(06)80010-6_bib18","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1287\/opre.6.3.419","article-title":"Constructing maximal dynamic flows from static flows","volume":"6","author":"Ford","year":"1958","journal-title":"Operations Research"},{"key":"10.1016\/S1574-6526(06)80010-6_bib19","series-title":"Proceedings of the Fifteenth Annual ACM Symposium on Theory of computing (STOC 1983)","first-page":"246","article-title":"A linear-time algorithm for a special case of disjoint set union","author":"Gabow","year":"1983"},{"key":"10.1016\/S1574-6526(06)80010-6_bib20","series-title":"Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S1574-6526(06)80010-6_bib21","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1002\/nav.3800140304","article-title":"Maximum matching in convex bipartite graphs","volume":"14","author":"Glover","year":"1967","journal-title":"Naval Research Logistics Quarterly"},{"key":"10.1016\/S1574-6526(06)80010-6_bib22","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1112\/jlms\/s1-10.37.26","article-title":"On representatives of subsets","volume":"10","author":"Hall","year":"1935","journal-title":"Journal of the London Mathematical Society"},{"key":"10.1016\/S1574-6526(06)80010-6_bib23","series-title":"Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming (CP 2004)","first-page":"290","article-title":"A Domain Consistency Algorithm for the Stretch Constraint","volume":"volume 3258","author":"Hellsten","year":"2004"},{"key":"10.1016\/S1574-6526(06)80010-6_bib24","series-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI)","first-page":"660","article-title":"Generality vs. specificity: an experience with AI and OR techniques","author":"Van Hentenryck","year":"1988"},{"key":"10.1016\/S1574-6526(06)80010-6_bib25","series-title":"Approximation Algorithms for NP-Hard Problems","year":"1996"},{"key":"10.1016\/S1574-6526(06)80010-6_bib26","series-title":"Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming (CP 2004)","first-page":"679","article-title":"A Hyper-Arc Consistency Algorithm for the Soft Alldifferent Constraint","volume":"volume 3258","author":"van Hoeve","year":"2004"},{"key":"10.1016\/S1574-6526(06)80010-6_bib27","doi-asserted-by":"crossref","DOI":"10.1007\/s10732-006-6550-4","article-title":"On Global Warming: Flow-Based Soft Global Constraints","author":"van Hoeve","year":"2006","journal-title":"Journal of Heuristics"},{"issue":"4","key":"10.1016\/S1574-6526(06)80010-6_bib28","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","article-title":"An n5\/2 algorithm for maximum matchings in bipartite graphs","volume":"2","author":"Hopcroft","year":"1973","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S1574-6526(06)80010-6_bib29","series-title":"Introduction to automata theory, languages, and computation","author":"Hopcroft","year":"1979"},{"key":"10.1016\/S1574-6526(06)80010-6_bib30","first-page":"27","article-title":"A new method of solving transportation-network problems","volume":"3","author":"Iri","year":"1960","journal-title":"Journal of the Operations Research Society of Japan"},{"key":"10.1016\/S1574-6526(06)80010-6_bib31","article-title":"Optimal Flows Through Networks","author":"Jewell","year":"1958"},{"key":"10.1016\/S1574-6526(06)80010-6_bib32","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","article-title":"A new polynomial-time algorithm for linear programming","volume":"4","author":"Karmarkar","year":"1984","journal-title":"Combinatorica"},{"key":"10.1016\/S1574-6526(06)80010-6_bib33","series-title":"Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC 1984)","first-page":"302","article-title":"A new polynomial-time algorithm for linear programming","author":"Karmarkar","year":"1984"},{"key":"10.1016\/S1574-6526(06)80010-6_bib34","series-title":"Proceedings of the Third International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2006)","article-title":"Expected-Case Analysis for Delayed Filtering","author":"Katriel","year":"2006"},{"issue":"3","key":"10.1016\/S1574-6526(06)80010-6_bib35","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/s10601-005-2237-y","article-title":"Complete bound consistency for the global cardinality constraint","volume":"10","author":"Katriel","year":"2005","journal-title":"Constraints"},{"key":"10.1016\/S1574-6526(06)80010-6_bib36","first-page":"191","article-title":"A polynomial algorithm in linear programming","volume":"20","author":"Khachiyan","year":"1979","journal-title":"Soviet Mathematics Doklady"},{"key":"10.1016\/S1574-6526(06)80010-6_bib37","series-title":"Proceedings of the First International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2004)","first-page":"200","article-title":"Filtering methods for symmetric cardinality constraint","volume":"volume 3011","author":"Kocjan","year":"2004"},{"key":"10.1016\/S1574-6526(06)80010-6_bib38","first-page":"116","article-title":"Graphok \u00e9s matrixok","volume":"38","author":"K\u00f6nig","year":"1931","journal-title":"Matematikai \u00e9s Fizikai Lapok"},{"issue":"1","key":"10.1016\/S1574-6526(06)80010-6_bib39","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0004-3702(78)90029-2","article-title":"A language and a program for stating and solving combinatorial problems","volume":"10","author":"Lauriere","year":"1978","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80010-6_bib40","series-title":"The Traveling Salesman Problem \u2014 A Guided Tour of Combinatorial Optimization","year":"1985"},{"key":"10.1016\/S1574-6526(06)80010-6_bib41","series-title":"Proceedings of the Second International Workshop on Constraint-based Reasoning (Constraint 1996)","first-page":"19","article-title":"A bounds-based reduction scheme for constraints of difference","author":"Leconte","year":"1996"},{"key":"10.1016\/S1574-6526(06)80010-6_bib42","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/BF00264533","article-title":"Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems","volume":"15","author":"Lipski","year":"1981","journal-title":"Acta Informatica"},{"key":"10.1016\/S1574-6526(06)80010-6_bib43","series-title":"Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI 2003)","first-page":"245","article-title":"A fast and simple algorithm for bounds consistency of the alldifferent constraint","author":"L\u00f3pez-Ortiz","year":"2003"},{"key":"10.1016\/S1574-6526(06)80010-6_bib44","series-title":"Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming (CP 2000)","first-page":"306","article-title":"Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint","volume":"volume 1894","author":"Mehlhorn","year":"2000"},{"key":"10.1016\/S1574-6526(06)80010-6_bib45","series-title":"Edge finding for cumulative scheduling","author":"Mercier","year":"2005"},{"key":"10.1016\/S1574-6526(06)80010-6_bib46","series-title":"Integer and Combinatorial Optimization","author":"Nemhauser","year":"1988"},{"key":"10.1016\/S1574-6526(06)80010-6_bib47","first-page":"55","article-title":"CHARME: Un langage industriel de programmation par contraintes, illustr\u00e9 par une application chez Renault","volume":"volume 1","author":"Oplobedu","year":"1989"},{"key":"10.1016\/S1574-6526(06)80010-6_bib48","series-title":"Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming (CP 2004)","first-page":"482","article-title":"A Regular Language Membership Constraint for Finite Sequences of Variables","volume":"volume 3258","author":"Pesant","year":"2004"},{"key":"10.1016\/S1574-6526(06)80010-6_bib49","series-title":"Proceedings of the Seventh International Conference on Principles and Practice of Constraint Programming (CP 2001)","first-page":"183","article-title":"A Filtering Algorithm for the Stretch Constraint","volume":"volume 2239","author":"Pesant","year":"2001"},{"key":"10.1016\/S1574-6526(06)80010-6_bib50","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF02392606","article-title":"Die Theorie der regul\u00e4ren graphs","volume":"15","author":"Petersen","year":"1891","journal-title":"Acta Mathematica"},{"key":"10.1016\/S1574-6526(06)80010-6_bib51","series-title":"Proceedings of the Seventh International Conference on Principles and Practice of Constraint Programming (CP 2001)","first-page":"451","article-title":"Specific Filtering Algorithms for Over-Constrained Problems","volume":"volume 2239","author":"Petit","year":"2001"},{"key":"10.1016\/S1574-6526(06)80010-6_bib52","series-title":"Proceedings of the Fifteenth National Conference on Artificial Intelligence and Tenth Innovative Applications of Artificial Intelligence Conference (AAAI\/IAAI)","first-page":"359","article-title":"A fast algorithm for the bound consistency of alldiff constraints","author":"Puget","year":"1998"},{"key":"10.1016\/S1574-6526(06)80010-6_bib53","series-title":"Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming (CP 2004)","first-page":"542","article-title":"Improved Algorithms for the Global Cardinality Constraint","volume":"volume 3258","author":"Quimper","year":"2004"},{"issue":"2","key":"10.1016\/S1574-6526(06)80010-6_bib54","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s10601-005-0552-y","article-title":"An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint","volume":"10","author":"Quimper","year":"2005","journal-title":"Constraints"},{"key":"10.1016\/S1574-6526(06)80010-6_bib55","series-title":"Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming (CP 2000)","first-page":"369","article-title":"Linear Formulation of Constraint Programming Models and Hybrid Solvers","volume":"volume 1894","author":"Refalo","year":"2000"},{"key":"10.1016\/S1574-6526(06)80010-6_bib56","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1023\/A:1020506526052","article-title":"Cost-Based Arc Consistency for Global Cardinality Constraints","volume":"7","author":"R\u00e9gin","year":"2002","journal-title":"Constraints"},{"key":"10.1016\/S1574-6526(06)80010-6_bib57","first-page":"362","article-title":"A Filtering Algorithm for Constraints of Difference in CSPs","volume":"volume 1","author":"R\u00e9gin","year":"1994"},{"key":"10.1016\/S1574-6526(06)80010-6_bib58","first-page":"209","article-title":"Generalized Arc Consistency for Global Cardinality Constraint","volume":"volume 1","author":"R\u00e9gin","year":"1996"},{"key":"10.1016\/S1574-6526(06)80010-6_bib59","series-title":"Proceedings of the Fifth International Conference on Principles and Practice of Constraint Programming (CP 1999)","first-page":"390","article-title":"Arc Consistency for Global Cardinality Constraints with Costs","volume":"volume 1713","author":"R\u00e9gin","year":"1999"},{"key":"10.1016\/S1574-6526(06)80010-6_bib60","series-title":"Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming (CP 2000)","first-page":"543","article-title":"An Original Constraint Based Approach for Solving over Constrained Problems","volume":"volume 1894","author":"R\u00e9gin","year":"2000"},{"key":"10.1016\/S1574-6526(06)80010-6_bib61","series-title":"Theory of Linear and Integer Programming","author":"Schrijver","year":"1986"},{"key":"10.1016\/S1574-6526(06)80010-6_bib62","series-title":"Combinatorial Optimization \u2013 Polyhedra and Efficiency","author":"Schrijver","year":"2003"},{"key":"10.1016\/S1574-6526(06)80010-6_bib63","series-title":"Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP 2003)","first-page":"679","article-title":"Approximated consistency for knapsack constraints","volume":"volume 2833","author":"Sellmann","year":"2003"},{"key":"10.1016\/S1574-6526(06)80010-6_bib64","series-title":"Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP 2003)","first-page":"694","article-title":"Cost-based filtering for shorter path constraints","volume":"volume 2833","author":"Sellmann","year":"2003"},{"key":"10.1016\/S1574-6526(06)80010-6_bib65","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S1574-6526(06)80010-6_bib66","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1023\/A:1021801522545","article-title":"A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints","volume":"118","author":"Trick","year":"2003","journal-title":"Annals of Operations Research"},{"key":"10.1016\/S1574-6526(06)80010-6_bib67","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/BF02952519","article-title":"Ein Satz \u00fcber Klasseneinteilungen von endlichen Mengen","volume":"5","author":"van der Waerden","year":"1927","journal-title":"Abhandlungen aus dem mathematischen Seminar der Hamburgischen Universit\u00e4t"},{"key":"10.1016\/S1574-6526(06)80010-6_bib68","series-title":"Approximation Algorithms","author":"Vazirani","year":"2001"}],"container-title":["Foundations of Artificial Intelligence","Handbook of Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1574652606800106?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1574652606800106?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T02:53:44Z","timestamp":1761620024000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1574652606800106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9780444527264"],"references-count":68,"URL":"https:\/\/doi.org\/10.1016\/s1574-6526(06)80010-6","relation":{},"ISSN":["1574-6526"],"issn-type":[{"value":"1574-6526","type":"print"}],"subject":[],"published":{"date-parts":[[2006]]}}}