{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T04:10:39Z","timestamp":1751429439178,"version":"3.41.0"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2002,9,1]],"date-time":"2002-09-01T00:00:00Z","timestamp":1030838400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,9,1]],"date-time":"2002-09-01T00:00:00Z","timestamp":1030838400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Global Optimization"],"published-print":{"date-parts":[[2002,9]]},"DOI":"10.1023\/a:1016246616462","type":"journal-article","created":{"date-parts":[[2002,12,29]],"date-time":"2002-12-29T02:48:35Z","timestamp":1041130115000},"page":"35-49","source":"Crossref","is-referenced-by-count":17,"title":["Search Heuristics for Box Decomposition Methods"],"prefix":"10.1007","volume":"24","author":[{"given":"Stefan","family":"Ratschan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"403121_CR1","doi-asserted-by":"crossref","unstructured":"Abramson, B. (1989), Control Strategies for Two-player Games, ACM Computing Surveys 21(2).","DOI":"10.1145\/66443.66444"},{"issue":"1","key":"403121_CR2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0004-3702(79)90003-1","volume":"12","author":"H. Berliner","year":"1979","unstructured":"Berliner, H. (1979), The B* tree search algorithm: A best-first proof procedure, Artificial Intelligence 12(1), 23\u201340.","journal-title":"Artificial Intelligence"},{"issue":"4","key":"403121_CR3","doi-asserted-by":"crossref","first-page":"323\u00b6","DOI":"10.1007\/BF02252252","volume":"57","author":"S. Berner","year":"1996","unstructured":"Berner, S. (1996), New results on Verified Global Optimization, Computing 57(4), 323\u00b6 343.","journal-title":"Computing"},{"key":"403121_CR4","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1023\/A:1021991817955","volume":"41","author":"L. G. Casado","year":"2001","unstructured":"Casado, L. G., Garc\u00eda, I. and Csendes, T. (2001), A Heuristic Rejection Criterion in Interval Global Optimization Algorithms, BIT 41, 683\u2013692.","journal-title":"BIT"},{"key":"403121_CR5","doi-asserted-by":"crossref","unstructured":"Caviness, B. F. and Johnson, J. R. (eds.) (1998), Quantifier Elimination and Cylindrical Algebraic Decomposition. Springer.","DOI":"10.1007\/978-3-7091-9459-1"},{"key":"403121_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1023\/A:1018952429396","volume":"90","author":"J. Clausen","year":"1999","unstructured":"Clausen, J. and Perregaard, M. (1999), On the best search strategy in parallel branch-and-bound: Best-first search versus lazy depth-first search, Annals of Operations Research 90, 1\u201317.","journal-title":"Annals of Operations Research"},{"key":"403121_CR7","first-page":"134","volume-title":"Second GI Conf. Automata Theory and Formal Languages","author":"G. E. Collins","year":"1975","unstructured":"Collins, G. E. (1975), Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition, in Second GI Conf. Automata Theory and Formal Languages, Vol. 33 of Lecture Notes in Computer Science. Springer, Berlin, pp. 134\u2013183. Also in (Caviness and Johnson, 1998)."},{"key":"403121_CR8","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1023\/A:1011228208051","volume":"19","author":"T. Csendes","year":"2001","unstructured":"Csendes, T. (2001), Convergence Properties of Interval Global Optimization algorithms with a New Class of Interval Selection Criteria, Journal of Global Optimization 19, 307\u2013327.","journal-title":"Journal of Global Optimization"},{"issue":"3","key":"403121_CR9","doi-asserted-by":"crossref","first-page":"922","DOI":"10.1137\/S0036142995281528","volume":"34","author":"T. Csendes","year":"1997","unstructured":"Csendes, T. and Ratz, D. (1997), Subdivision Direction Selection in Interval Methods for Global Optimization, SIAM Journal on Numerical Analysis 34(3), 922\u2013938.","journal-title":"SIAM Journal on Numerical Analysis"},{"issue":"3","key":"403121_CR10","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1145\/3828.3830","volume":"32","author":"R. Dechter","year":"1985","unstructured":"Dechter, R. and Pearl, J. (1985), Generalized Best-First Search Strategies and the Optimality of A*, Journal of the ACM 32(3), 505\u2013536.","journal-title":"Journal of the ACM"},{"key":"403121_CR11","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1006\/jsco.1997.0120","volume":"24","author":"P. Dorato","year":"1997","unstructured":"Dorato, P., Yang, W. and Abdallah, C. (1997), Robust Multi-Objective Feedback Design by Quantifier Elimination, Journal of Symbolic Computation 24, 153\u2013159.","journal-title":"Journal of Symbolic Computation"},{"key":"403121_CR12","unstructured":"Ebbinghaus, H.-D., Flum, J. and Thomas, W. (1984), Mathematical Logic. Springer Verlag."},{"issue":"3","key":"403121_CR13","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1023\/A:1009617818678","volume":"5","author":"H. Farreny","year":"1999","unstructured":"Farreny, H. (1999), Completeness and Admissibility for General Heuristic Search Algorithms-A Theoretical Study: Basic Concepts and Proofs, Journal of Heuristics 5(3), 353\u2013376.","journal-title":"Journal of Heuristics"},{"key":"403121_CR14","unstructured":"Fernandez, A. and Hill, P. (2001), Branching: The Essence of Constraint Solving, In: Proceedings of the Sixth Annual Workshop of the ERCIM Working Group on Constraints. http:\/\/arXiv.org\/html\/cs\/0110012."},{"key":"403121_CR15","unstructured":"Hansen, E. (1992), Global Optimization Using Interval Analysis. Marcel Dekker, Inc."},{"key":"403121_CR16","doi-asserted-by":"crossref","unstructured":"Hentenryck, P. V. (1997), Numerica: A Modeling Language for Global Optimization, in Proceedings of the 15th International Joint Conference on Artificial Intelligence. Nagoya, Japan.","DOI":"10.7551\/mitpress\/5073.001.0001"},{"key":"403121_CR17","doi-asserted-by":"crossref","unstructured":"Hong, H. (1992), Heuristic Search Strategies for Cylindrical Algebraic Decomposition, in Calmet et al., J. (eds.), Proceedings of Artificial Intelligence and Symbolic Mathematical Computing, Springer Lecture Notes in Computer Science 737, pp. 152\u2013165.","DOI":"10.1007\/3-540-57322-4_10"},{"key":"403121_CR18","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/BF02307383","volume":"53","author":"H. Hong","year":"1994","unstructured":"Hong, H. and Stahl, V. (1994), Safe Starting Regions by Fixed Points and Tightening, Computing 53, 323\u2013335.","journal-title":"Computing"},{"issue":"4","key":"403121_CR19","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF00998631","volume":"5","author":"T. Ibaraki","year":"1976","unstructured":"Ibaraki, T. (1976), Theoretical comparisons of search strategies in branch-and-bound algorithms, International Journal of Computer and Information Sciences 5(4), 315\u2013344.","journal-title":"International Journal of Computer and Information Sciences"},{"key":"403121_CR20","doi-asserted-by":"crossref","unstructured":"Ibaraki, T. (1978), Branch-and-Bound Procedure and State-Space Representation of Combinatorial Optimization Problems, Information and Control pp. 1\u201327.","DOI":"10.1016\/S0019-9958(78)90197-3"},{"key":"403121_CR21","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0004-3702(86)90092-5","volume":"29","author":"T. Ibaraki","year":"1986","unstructured":"Ibaraki, T. (1986), Generalization of Alpha-Beta and SSS* Search Procedures, Artificial Intelligence 29, 73\u2013117.","journal-title":"Artificial Intelligence"},{"key":"403121_CR22","volume-title":"Applied Interval Analysis, with Examples in Parameter and State Estimation, Robust Control and Robotics","author":"L. Jaulin","year":"2001","unstructured":"Jaulin, L., Kieffer, M. Didrit, O. and Walter, E. (2001a), Applied Interval Analysis, with Examples in Parameter and State Estimation, Robust Control and Robotics. Springer, Berlin."},{"key":"403121_CR23","doi-asserted-by":"crossref","unstructured":"Jaulin, L., Kieffer, M. Didrit, O. and Walter, E. (2001b), Dealing with Quantifiers, Chapt. 5.6.3, pp. 126\u2013134. In (Jaulin et al., 2001a).","DOI":"10.1007\/978-1-4471-0249-6_1"},{"key":"403121_CR24","unstructured":"Jaulin, L., Kieffer, M., Didrit, O. and Walter, E. (2001c), Minimax Optimization, Chapt. 5.6, pp. 133\u2013134. In (Jaulin et al., 2001a)."},{"issue":"2","key":"403121_CR25","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/BF02276877","volume":"57","author":"R. B. Kearfott","year":"1996","unstructured":"Kearfott, R. B. (1996a), Interval Extensions of Non-Smooth Functions for Global Optimization and Nonlinear Systems Solvers, Computing 57(2), 149\u2013162.","journal-title":"Computing"},{"key":"403121_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2495-0","volume-title":"Rigorous Global Search: Continuous Problems","author":"R. B. Kearfott","year":"1996","unstructured":"Kearfott, R. B. (1996b), Rigorous Global Search: Continuous Problems. Kluwer Academic Publishers, Dordrecht."},{"issue":"3","key":"403121_CR27","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/212094.212120","volume":"27","author":"R. E. Korf","year":"1995","unstructured":"Korf, R. E. (1995), Space-Efficient Search Algorithms, Computing Surveys 27(3), 337\u2013339.","journal-title":"Computing Surveys"},{"issue":"1\u00b6 2","key":"403121_CR28","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0004-3702(95)00096-8","volume":"84","author":"R. E. Korf","year":"1996","unstructured":"Korf, R. E. and Chickering, D. M. (1996), Best-first Minimax Search, Artificial Intelligence 84(1\u00b6 2), 299\u2013337.","journal-title":"Artificial Intelligence"},{"key":"403121_CR29","doi-asserted-by":"crossref","unstructured":"Kumar, V. and Kanal, L. (1983), A General Branch and Bound Formulation for Understanding and Synthesizing And\/Or Tree Search Procedures, in Pearl, J. (ed.), Search and Heuristics. North-Holland.","DOI":"10.1016\/S0004-3702(83)80009-5"},{"key":"403121_CR30","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/978-1-4613-8788-6_3","volume-title":"Search in Artificial Intelligence","author":"V. Kumar","year":"1988","unstructured":"Kumar, V., Nau, D. S. and Kanal, L. N. (1988), A General Branch-And-Bound Formulation for AND\/OR Graph and Game Tree Search, in Kanal, L. and Kumar, V. (eds.), Search in Artificial Intelligence. Springer, Berlin, pp. 91\u2013130."},{"key":"403121_CR31","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1287\/opre.14.4.699","volume":"14","author":"E. L. Lawler","year":"1966","unstructured":"Lawler, E. L. and Wood, D. E. (1966), Branch-and-Bound Methods: A Survey, Operations Research 14, 699\u2013719.","journal-title":"Operations Research"},{"key":"403121_CR32","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1145\/2455.2459","volume":"32","author":"A. Mahanti","year":"1985","unstructured":"Mahanti, A. and Bagchi, A. (1985), AND\/OR graph heuristic search methods, Journal of the ACM 32, 28\u201351.","journal-title":"Journal of the ACM"},{"issue":"5","key":"403121_CR33","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1093\/comjnl\/36.5.432","volume":"36","author":"S. McCallum","year":"1993","unstructured":"McCallum, S. (1993), Solving Polynomial Strict Inequalities Using Cylindrical Algebraic Decomposition, The Computer Journal 36(5), 432\u2013438.","journal-title":"The Computer Journal"},{"key":"403121_CR34","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1287\/opre.18.1.24","volume":"18","author":"L. G. Mitten","year":"1970","unstructured":"Mitten, L. G. (1970), Branch-and-bound methods: General formulation and properties, Operations Research 18, 24\u201334. Errata in Vol. 19, p. 550.","journal-title":"Operations Research"},{"key":"403121_CR35","volume-title":"Interval Analysis","author":"R. E. Moore","year":"1966","unstructured":"Moore, R. E. (1966), Interval Analysis. Prentice Hall, Englewood Cliffs, NJ."},{"key":"403121_CR36","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/BF01580772","volume":"41","author":"R. E. Moore","year":"1988","unstructured":"Moore, R. E. and Ratschek, H. (1988), Inclusion Functions and Global Optimization II, Mathematical Programming 41, 341\u2013356.","journal-title":"Mathematical Programming"},{"key":"403121_CR37","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-09438-9","volume-title":"Principles of Artificial Intelligence","author":"N. J. Nilsson","year":"1982","unstructured":"Nilsson, N. J. (1982), Principles of Artificial Intelligence. Springer, Berlin."},{"issue":"2","key":"403121_CR38","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0004-3702(82)90034-0","volume":"19","author":"A. J. Palay","year":"1982","unstructured":"Palay, A. J. (1982), The B* tree search algorithm: New Results, Artificial Intelligence 19(2), 145\u2013163.","journal-title":"Artificial Intelligence"},{"key":"403121_CR39","volume-title":"Searching with Probabilities","author":"A. J. Palay","year":"1985","unstructured":"Palay, A. J. (1985), Searching with Probabilities. Pitman, London."},{"key":"403121_CR40","unstructured":"Pearl, J. (1984), Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, Reading, MA."},{"key":"403121_CR41","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0004-3702(95)00126-3","volume":"87","author":"A. Plaat","year":"1996","unstructured":"Plaat, A., Schaeffer, J., Pijls, W. and de Bruin, A. (1996), Best-first Fixed-Depth Minimax Algorithms, Artificial Intelligence 87, 255\u2013293.","journal-title":"Artificial Intelligence"},{"key":"403121_CR42","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1023\/A:1008236911603","volume":"13","author":"J.-F. Puget","year":"1998","unstructured":"Puget, J.-F. and Hentenryck, P. V. (1998), A Constraint Satisfaction Approach to a Circuit Design Problem, Journal of Global Optimization 13, 75\u201393.","journal-title":"Journal of Global Optimization"},{"key":"403121_CR43","unstructured":"Ratschan, S. (2000a), Convergence of Quantified Constraint Solving by Approximate Quantifiers, Technical Report 00-23, Research Institute for Symbolic Computation (RISC) \u00b6Linz. Submitted for Publication."},{"issue":"1","key":"403121_CR44","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1023\/A:1014785518570","volume":"8","author":"S. Ratschan","year":"2002","unstructured":"Ratschan, S. (2002), Approximate Quantified Constraint Solving by Cylindrical Box Decomposition. Reliable Computing, 8(1): 21\u201342.","journal-title":"Reliable Computing"},{"key":"403121_CR45","doi-asserted-by":"crossref","unstructured":"Ratschan, S. (2002), Continuous First-Order Constraint Satisfaction. In Artificial Intelligence, Automated Reasoning, and Symbolic Computation, number 2385 in LNCS. Springer.","DOI":"10.1007\/3-540-45470-5_18"},{"issue":"4","key":"403121_CR46","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1006\/jsco.2001.0519","volume":"33","author":"S. Ratschan","year":"2002","unstructured":"Ratschan, S. (2002), Quantified Constraints Under Perturbations. Journal of Symbolic Computation, 33(4): 493\u2013505. To appear.","journal-title":"Journal of Symbolic Computation"},{"issue":"4","key":"403121_CR47","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/BF01096417","volume":"3","author":"H. Ratschek","year":"1993","unstructured":"Ratschek, H. and Rokne, J. (1993), Experiments Using Interval Analysis For Solving a Circuit Design Problem, Journal of Global Optimization 3(4), 501\u2013518. SEARCH HEURISTICS FOR BOX DECOMPOSITION METHODS 49","journal-title":"Journal of Global Optimization"},{"key":"403121_CR48","volume-title":"New Computer Methods for Global Optimizations","author":"H. Ratschek","year":"1988","unstructured":"Ratschek, H. and Rokne, J. (1988), New Computer Methods for Global Optimizations. Ellis Horwood Limited, Chichester, UK."},{"key":"403121_CR49","unstructured":"Ratz, D. (1992), Automatische Ergebnisverifikation bei globalen Optimierungsproblemen, Ph.D. thesis, Universit\u00e4t Karlsruhe."},{"issue":"2","key":"403121_CR50","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/0004-3702(94)90049-3","volume":"71","author":"A. Reinefeld","year":"1994","unstructured":"Reinefeld, A. and Ridinger, P. (1994), Time-Efficient State Space Search, Artificial Intelligence 71(2), 397\u2013408.","journal-title":"Artificial Intelligence"},{"key":"403121_CR51","unstructured":"Schmidt, D. A. (1988), Denotational Semantics: A Methodology for Language Development. W.C. Brown."},{"issue":"1","key":"403121_CR52","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02388185","volume":"2","author":"S. P. Shary","year":"1996","unstructured":"Shary, S. P. (1996), Algebraic Approach to the Interval Linear Static Identification, Tolerance, and Control Problems, or One More Application of Kaucher Arithmetic, Reliable Computing 2(1), 3\u201333.","journal-title":"Reliable Computing"},{"key":"403121_CR53","doi-asserted-by":"crossref","first-page":"742","DOI":"10.1007\/BF01933221","volume":"30","author":"Z. Shen","year":"1990","unstructured":"Shen, Z., Neumaier, A. and Eiermann, M. C. (1990), Solving Minimax Problems by Interval Methods, BIT 30, 742\u2013751.","journal-title":"BIT"},{"key":"403121_CR54","doi-asserted-by":"crossref","unstructured":"Stewart, B. S., Liaw, C.-F. and C. C. W. III, (1994), A Bibliography of Heuristic Search Research Through 1992, IEEE Transactions on Systems, Man, and Cybernetics 24(2).","DOI":"10.1109\/21.281425"},{"key":"403121_CR55","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0004-3702(79)90016-X","volume":"12","author":"G. C. Stockman","year":"1979","unstructured":"Stockman, G. C. (1979), A Minimax Algorithm Better than Alpha-Beta?, Artificial Intelligence 12, 179\u2013196.","journal-title":"Artificial Intelligence"},{"key":"403121_CR56","doi-asserted-by":"crossref","first-page":"922","DOI":"10.1109\/TSE.1985.232550","volume":"11","author":"B.W. Wah","year":"1985","unstructured":"Wah, B.W. and Yu, C. F. (1985), Stochastic modeling of branch-and-bound algorithms with best-first search, IEEE Trans. Software Eng. SE-11, 922\u2013934.","journal-title":"IEEE Trans. Software Eng."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1016246616462.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1016246616462\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1016246616462.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T10:44:14Z","timestamp":1751366654000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1016246616462"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,9]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,9]]}},"alternative-id":["403121"],"URL":"https:\/\/doi.org\/10.1023\/a:1016246616462","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2002,9]]}}}