{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T17:20:47Z","timestamp":1790875247159,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":51,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540602996","type":"print"},{"value":"9783540447887","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60299-2_35","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:15:31Z","timestamp":1330280131000},"page":"564-587","source":"Crossref","is-referenced-by-count":11,"title":["Constraint solving for combinatorial search problems: A tutorial"],"prefix":"10.1007","author":[{"given":"P.","family":"Hentenryck","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"35_CR1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0167-5060(08)70342-X","volume":"5","author":"E. Balas","year":"1979","unstructured":"E. Balas. Disjunctive Programming. Annals of Discrete Mathematics, 5:3\u201351, 1979.","journal-title":"Annals of Discrete Mathematics"},{"key":"35_CR2","volume-title":"Dynamic Programming","author":"R.E. Bellman","year":"1957","unstructured":"R.E. Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, 1957."},{"key":"35_CR3","unstructured":"F. Benhamou, D. McAllester, and P. Van Hentenryck. CLP (Intervals) Revisited. In Proceedings of the International Symposium on Logic Programming (ILPS-94), pages 124\u2013138, Ithaca, NY, November 1994."},{"key":"35_CR4","unstructured":"A. Bockmayr. 0\u20131 Constraints and 0\u20131 Optimization. In Proc. 3rd Workshop on Constraint Logic Programming, Marseilles, France, 1993."},{"key":"35_CR5","unstructured":"Maurice Bruynooghe. In J.L. Lassez and G. Plotkin, editors, Computational Logic, Essays in Honour of Alan Robinson, pages 166\u2013177. Cambridge, Massachusetts."},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"B. Buchberger. Groebner Bases: An Algorithmic Method in Polynomial Ideal Theory. In Multidimensional Systems Theory, pages 184\u2013232. N.K. Bose Ed., D. Reidel Publishing Co., 1985.","DOI":"10.1007\/978-94-009-5225-6_6"},{"key":"35_CR7","volume-title":"Technical Report ISSN 0294-2755","author":"J. Carlier","year":"1986","unstructured":"J. Carlier and E. Pinson. Une M\u00e9thode Arborescente pour Optimiser la Dur\u00e9e d'un JOB-SHOP. Technical Report ISSN 0294-2755, I.M.A, Angers, 1986."},{"key":"35_CR8","unstructured":"Y. Caseau, P.-Y. Guillo, and E. Leveriez. A Deductive and Object-Oriented Approach to a Complex Scheduling Problem. In Proc. of DOOD'93, Phoenix, AZ, December 1989."},{"key":"35_CR9","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01580109","volume":"5","author":"V. Chv\u00e1tal","year":"1973","unstructured":"V. Chv\u00e1tal. Edmonds Polytopes and Weakly Hamiltonian Graphs. Mathematical Programming, 5:29\u201340, 1973.","journal-title":"Mathematical Programming"},{"key":"35_CR10","volume-title":"Guarded Constructive Disjunction: Angel or Demon?","author":"C. Codognet","year":"1995","unstructured":"C. Codognet and P. Codognet. Guarded Constructive Disjunction: Angel or Demon? In First International Conference on Principles and Practice of Constraint Programming (CP'95), Cassis, France, September 1995. Springer Verlag."},{"key":"35_CR11","first-page":"134","volume-title":"Lecture Notes In Computer Science, Vol. 33","author":"G.E. Collins","year":"1975","unstructured":"G.E. Collins. Quantifier Elimination for the Elementary Theory of Real Closed Fields by Cylindrical Algebraic Decomposition. In Lecture Notes In Computer Science, Vol. 33, pages 134\u2013183. Springer Verlag, Berlin, 1975."},{"issue":"4","key":"35_CR12","first-page":"412","volume":"28","author":"A. Colmerauer","year":"1990","unstructured":"A. Colmerauer. An Introduction to Prolog III. Commun. ACM, 28(4):412\u2013418, 1990.","journal-title":"Commun. ACM"},{"key":"35_CR13","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, 1990."},{"issue":"2","key":"35_CR14","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1002\/nav.3800060109","volume":"5","author":"G.B. Dantzig","year":"1959","unstructured":"G.B. Dantzig. A Note on Solving Linear Programs in Integers. Naval Research, 5(2):75\u201376, 1959.","journal-title":"Naval Research"},{"key":"35_CR15","volume-title":"Linear Programming and Extensions","author":"G.B. Dantzig","year":"1963","unstructured":"G.B. Dantzig. Linear Programming and Extensions. Princeton University Press, Princeton, N.J., 1963."},{"key":"35_CR16","first-page":"393","volume":"2","author":"G.B. Dantzig","year":"1955","unstructured":"G.B. Dantzig, D.R. Fulkerson, and S.M. Johnson. Solution of a Large-Scale Travelling Salesman Problem. Operations Research, 2:393\u2013410, 1955.","journal-title":"Operations Research"},{"key":"35_CR17","unstructured":"B. de Backer and H. Beringer. A clp language handling disjunctions of linear constraints. In Proceedings of the Tenth International Conference on Logic Programming (ICLP-93), Budapest (Hungary), June 1993."},{"key":"35_CR18","unstructured":"R. Dechter. Constraint Networks. In Encyclopedia of Artificial Intelligence (Second Edition). Stuart C. Shapiro Editor, Wiley, 1992."},{"key":"35_CR19","volume-title":"Numerical Methods for Unconstrained Optimization and Nonlinear Equations","author":"J.E. Dennis","year":"1983","unstructured":"J.E. Dennis and R.B. Schnabel. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice Hall, Englewood Cliff's, New Jersey, 1983."},{"key":"35_CR20","unstructured":"M. Dincbas, P. Van Hentenryck, H. Simonis, A. Aggoun, T. Graf, and F. Berthier. The Constraint Logic Programming Language CHIP. In Proceedings of the International Conference on Fifth Generation Computer Systems, Tokyo, Japan, December 1988."},{"key":"35_CR21","doi-asserted-by":"crossref","unstructured":"E. Freuder. Partial Constraint Satisfaction. Artificial Intelligence, 58, 1992.","DOI":"10.1016\/0004-3702(92)90004-H"},{"key":"35_CR22","volume-title":"Integer Programming","author":"R.S. Garfinkel","year":"1972","unstructured":"R.S. Garfinkel and G.L. Nemhauser. Integer Programming. John Wiley & Sons, New York, 1972."},{"key":"35_CR23","volume-title":"Principles and Practice of Constraint Programming","author":"M. Gleicher","year":"1995","unstructured":"M. Gleicher. Practical Issues in Programming Constraints. In V. Saraswat and P. Van Hentenryck, editors, Principles and Practice of Constraint Programming. The MIT Press, Cambridge, Massachusetts, 1995."},{"key":"35_CR24","unstructured":"R.E. Gomory. An Algorithm for Integer Solutions to Linear Programs. In R. Graves and P. Wolfe, editors, Recent advances in Mathematical Programming, pages 269\u2013302. McGraw-Hill, 1963."},{"key":"35_CR25","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1073\/pnas.53.2.260","volume":"53","author":"R.E. Gomory","year":"1965","unstructured":"R.E. Gomory. On the Relation between Integer and Non-Integer Solutions to Linear Programs. Proceedings of the National Academy of Science, 53:260\u2013265, 1965.","journal-title":"Proceedings of the National Academy of Science"},{"key":"35_CR26","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0096-3003(83)90001-2","volume":"12","author":"E.R. Hansen","year":"1983","unstructured":"E.R. Hansen and R.I. Greenberg. An Interval Newton Method. Appl. Math. Comput., 12:89\u201398, 1983.","journal-title":"Appl. Math. Comput."},{"issue":"3\u20134","key":"35_CR27","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/BF02307383","volume":"53","author":"H. Hong","year":"1994","unstructured":"H. Hong and V. Stahl. Safe Starting Regions by Fixed Points and Tightening. Computing, 53(3\u20134):323\u2013335, 1994.","journal-title":"Computing"},{"issue":"3","key":"35_CR28","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1145\/129393.129398","volume":"14","author":"J. Jaffar","year":"1992","unstructured":"J. Jaffar, S. Michaylov, P.J. Stuckey, and R. Yap. The CLP(\u211c) language and system. ACM Trans. on Programming Languages und Systems, 14(3):339\u2013395, 1992.","journal-title":"ACM Trans. on Programming Languages und Systems"},{"key":"35_CR29","doi-asserted-by":"crossref","unstructured":"D. Kapur, T. Saxena, and L. Yang. Algebraic and Geometric Reasoning using Dixon Resultants. In Proceedings of Intl. Symp. on Symbolic and Algebraic Computation (ISSAC-94), pages 99\u2013107, Oxford, England, July 1994.","DOI":"10.1145\/190347.190372"},{"key":"35_CR30","doi-asserted-by":"crossref","first-page":"2245","DOI":"10.1002\/j.1538-7305.1965.tb04146.x","volume":"44","author":"S. Lin","year":"1965","unstructured":"S. Lin. Computer Solutions of the Travelling Salesman Problem. Bell System Tech. Journal, 44:2245\u20132269, 1965.","journal-title":"Bell System Tech. Journal"},{"issue":"1","key":"35_CR31","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"A.K. Mackworth","year":"1977","unstructured":"A.K. Mackworth. Consistency in Networks of Relations. Artificial Intelligence, 8(1):99\u2013118, 1977.","journal-title":"Artificial Intelligence"},{"key":"35_CR32","unstructured":"A.K. Mackworth. Constraint Satisfaction. In Encyclopedia of Artificial Intelligence (Second Edition). Stuart C. Shapiro Editor, Wiley, 1992."},{"key":"35_CR33","volume-title":"Principles and Practice of Constraint Programming","author":"K. McAloon","year":"1995","unstructured":"K. McAloon and C. Tretkoff. 2LP: Linear Programming and Logic Programming. In V. Saraswat and P. Van Hentenryck, editors, Principles and Practice of Constraint Programming. The MIT Press, Cambridge, Massachusetts, 1995."},{"key":"35_CR34","unstructured":"S. Minton, M.D. Johnston, and A.B. Philips. Solving Large-Scale Constraint Satisfaction and Scheduling Problems using a Heuristic Repair Method. In AAAI-90, August 1990."},{"issue":"2","key":"35_CR35","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U. Montanari","year":"1974","unstructured":"U. Montanari. Networks of Constraints: Fundamental Properties and Applications to Picture Processing. Information Science, 7(2):95\u2013132, 1974.","journal-title":"Information Science"},{"key":"35_CR36","doi-asserted-by":"crossref","unstructured":"U. Montanari and F. Rossi. An efficient algorithm for the solution of hierarchical networks of constraints. In Workshop on Graph Grammars and Their Applications in Computer Science, Warrenton, December 1986.","DOI":"10.1007\/3-540-18771-5_69"},{"key":"35_CR37","volume-title":"Solving Polynomial Systems Using Continuation for Scientific and Engineering Problems","author":"A.P. Morgan","year":"1987","unstructured":"A.P. Morgan. Solving Polynomial Systems Using Continuation for Scientific and Engineering Problems. Prentice-Hall, Englewood Cliffs, NJ, 1987."},{"key":"35_CR38","doi-asserted-by":"crossref","unstructured":"G. Nelson. Juno, a constraint-based graphics system. In ACM SIGGRAPH'85, pages 301\u2013309, San Francisco, CA, July 1985.","DOI":"10.1145\/325334.325241"},{"key":"35_CR39","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer und Combinatorial Optimization","author":"G.L. Nemhauser","year":"1988","unstructured":"G.L. Nemhauser and L.A. Wolsey. Integer und Combinatorial Optimization. John Wiley & Sons, New York, 1988."},{"key":"35_CR40","unstructured":"W. Older and A. Vellino. Extending Prolog with Constraint Arithmetics on Real Intervals. In Canadian Conference on Computer & Electrical Engineering, Ottawa, 1990."},{"key":"35_CR41","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/S0167-5060(08)70831-8","volume":"4","author":"M. W. Padberg","year":"1979","unstructured":"M. W. Padberg. Covering, Packing, and Knapsack Problems. Annals of Discrete Mathematics, 4:265\u2013287, 1979.","journal-title":"Annals of Discrete Mathematics"},{"key":"35_CR42","unstructured":"J.F. Puget and P. Albert. PECOS: Programmation par Contraintes Orientee Objets. Genie Logiciel and Systemes Experts, 23, 1991."},{"key":"35_CR43","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/B978-0-12-505630-4.50012-2","volume-title":"Reliability in Computing","author":"S.M. Rump","year":"1988","unstructured":"S.M. Rump. Algorithm for Verified Inclusions-Theory and Practice. In Reliability in Computing, pages 109\u2013126. Academic Press, San Diego, 1988."},{"key":"35_CR44","unstructured":"H.M. Salkin and K. Mathur. Foundations of Integer Programming. North-Holland, 1989."},{"key":"35_CR45","unstructured":"B. Selman, H. Levesque, and D. Mitchell. A NEw Method for Solving Hard Satisfiability Problems. In AAAI-92, pages 440\u2013446, 1992."},{"key":"35_CR46","volume-title":"Logic Programming Series","author":"P. Hentenryck Van","year":"1989","unstructured":"P. Van Hentenryck. Constraint Satisfaction in Logic Programming. Logic Programming Series, The MIT Press, Cambridge, Mass., 1989."},{"key":"35_CR47","unstructured":"P. Van Hentenryck and Y. Deville. The Cardinality Operator: A New Logical Connective and Its Application to Constraint Logic Programming. In Eighth International Conference on Logic Programming (ICLP-91), Paris (France), June 1991."},{"key":"35_CR48","unstructured":"P. Van Hentenryck, D. McAllister, and D. Kapur. Solving Polynomial Systems Using a Branch and Prune Approach. SIAM Journal on Numerical Analysis, 1995. (to appear)."},{"key":"35_CR49","doi-asserted-by":"crossref","unstructured":"P. Van Hentenryck, V. Saraswat, and Y. Deville. The Design, Implementation, and Evaluation of the Constraint Language cc(FD). In Constraint Programming: Basics and Trends. Springer Verlag, 1995.","DOI":"10.1007\/3-540-59155-9_15"},{"issue":"3","key":"35_CR50","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1137\/0731049","volume":"31","author":"J. Verschelde","year":"1994","unstructured":"J. Verschelde, P. Verlinden, and R. Cools. Homotopies Exploiting Newton Polytopes For Solving Sparse Polynomial Systems. SIAM Journal on Numerical Analysis, 31(3):915\u2013930, 1994.","journal-title":"SIAM Journal on Numerical Analysis"},{"key":"35_CR51","unstructured":"D. Waltz. Generating Semantic Descriptions from Drawings of Scenes with Shadows. Technical Report AI271, MIT, MA, November 1972."}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming \u2014 CP '95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60299-2_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T16:52:37Z","timestamp":1713631957000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60299-2_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602996","9783540447887"],"references-count":51,"URL":"https:\/\/doi.org\/10.1007\/3-540-60299-2_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}