{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T07:01:54Z","timestamp":1770966114173,"version":"3.50.1"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"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":[[1998,1]]},"DOI":"10.1023\/a:1008287028851","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T13:47:34Z","timestamp":1040564854000},"page":"61-99","source":"Crossref","is-referenced-by-count":88,"title":["A Discrete Lagrangian-Based Global-Search Method for Solving Satisfiability Problems"],"prefix":"10.1007","volume":"12","author":[{"given":"Yi","family":"Shang","sequence":"first","affiliation":[]},{"given":"Benjamin W.","family":"Wah","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"140027_CR1","volume-title":"Studies in Linear and Nonlinear Programming","author":"K. J. Arrow","year":"1958","unstructured":"K. J. Arrow and L. Hurwicz. Gradient method for concave programming, I: Local results. In K. J. Arrow, L. Hurwica, and H. Uzawa, editors, Studies in Linear and Nonlinear Programming. Stanford University Press, Stanford, CA, 1958."},{"key":"140027_CR2","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF00940812","volume":"45","author":"V. Cerny","year":"1985","unstructured":"V. Cerny. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45: 41\u201351, 1985.","journal-title":"Journal of Optimization Theory and Applications"},{"key":"140027_CR3","first-page":"156","volume-title":"Proc. Computer Software and Applications Conference","author":"Y.-J. Chang","year":"1995","unstructured":"Y.-J. Chang and B. W. Wah. Lagrangian techniques for solving a class of zero-one integer linear programs. In Proc. Computer Software and Applications Conference, pages 156\u2013161, Dallas, TX, August 1995. IEEE."},{"key":"140027_CR4","doi-asserted-by":"crossref","unstructured":"A. Cichocki and R. Unbehauen. Switched-capacitor artificial neural networks for nonlinear optimization with constraints. In Proc. of 1990 IEEE Int'l Symposium on Circuits and Systems, pages 2809\u20132812, 1990.","DOI":"10.1109\/ISCAS.1990.112594"},{"key":"140027_CR5","unstructured":"A. Davenport, E. Tsang, C. Wang, and K. Zhu. Genet: A connectionist architecture for solving constraint satisfaction problems by iterative improvement. In Proc. of the 12th National Conf. on Artificial Intelligence, pages 325\u2013330, Seattle, WA, 1994."},{"key":"140027_CR6","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M. Davis","year":"1960","unstructured":"M. Davis and H. Putnam. A computing procedure for quantification theory. J. Assoc. Comput. Mach., 7: 201\u2013215, 1960.","journal-title":"J. Assoc. Comput. Mach."},{"key":"140027_CR7","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0167-6377(89)90002-3","volume":"8","author":"T. Feo","year":"1989","unstructured":"T. Feo and M. Resende. A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, (8): 67\u201371, 1989.","journal-title":"Operations Research Letters"},{"key":"140027_CR8","volume-title":"Greedy randomized adaptive search procedures","author":"T. Feo","year":"1994","unstructured":"T. Feo and M. Resende. Greedy randomized adaptive search procedures. Technical report, AT&T Bell Laboratories, Murray Hill, NJ 07974, February 1994."},{"key":"140027_CR9","doi-asserted-by":"crossref","unstructured":"B. Gavish and S. L. Hantler. An algorithm for optimal route selection in SNA networks. IEEE Transactions on Communications, pages 1154\u20131161, 1983.","DOI":"10.1109\/TCOM.1983.1095752"},{"key":"140027_CR10","unstructured":"M. R. Genesereth and N. J. Nilsson. Logical Foundation of Artificial Intelligence. Morgan Kaufmann, 1987."},{"key":"140027_CR11","unstructured":"I. Gent and T. Walsh. Towards an understanding of hill-climbing procedures for SAT. In Proc. of the 11th National Conf. on Artificial Intelligence, pages 28\u201333, Washington, DC, 1993."},{"key":"140027_CR12","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/BFb0120690","volume":"2","author":"A. M. Geoffrion","year":"1974","unstructured":"A. M. Geoffrion. Lagrangian relaxation and its uses in integer programming. Mathematical Programming Study, 2: 82\u2013114, 1974.","journal-title":"Mathematical Programming Study"},{"issue":"3","key":"140027_CR13","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F. Glover","year":"1989","unstructured":"F. Glover. Tabu search \u2014 Part I. ORSA J. Computing, 1(3): 190\u2013206, 1989.","journal-title":"ORSA J. Computing"},{"key":"140027_CR14","unstructured":"J. Gu. Parallel Algorithms and Architectures for Very Fast AI Search. PhD thesis, Dept. of Computer Science, University of Utah, August 1989."},{"key":"140027_CR15","series-title":"Technical Report","volume-title":"How to solve very large-scale satisfiability (VLSS) problems","author":"J. Gu","year":"1990","unstructured":"J. Gu. How to solve very large-scale satisfiability (VLSS) problems. Technical Report UCECETR-90-002, Univ. of Calgary, Canada, October 1990."},{"issue":"1","key":"140027_CR16","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1145\/130836.130837","volume":"3","author":"J. Gu","year":"1992","unstructured":"J. Gu. Efficient local search for very large-scale satisfiability problems. SIGART Bulletin, 3(1): 8\u201312, January 1992.","journal-title":"SIGART Bulletin"},{"key":"140027_CR17","doi-asserted-by":"crossref","unstructured":"J. Gu. On optimizing a search problem. In N. G. Bourbakis, editor, Artificial Intelligence Methods and Applications. World Scientific Publishers, 1992.","DOI":"10.1142\/9789814354707_0002"},{"issue":"8","key":"140027_CR18","first-page":"865","volume":"14","author":"J. Gu","year":"1992","unstructured":"J. Gu. The UniSAT problem models (appendix). IEEE Trans. on Pattern Analysis and Machine Intelligence, 14(8): 865, Aug 1992.","journal-title":"IEEE Trans. on Pattern Analysis and Machine Intelligence"},{"issue":"4","key":"140027_CR19","doi-asserted-by":"crossref","first-page":"1108","DOI":"10.1109\/21.247892","volume":"23","author":"J. Gu","year":"1993","unstructured":"J. Gu. Local search for satisfiability (SAT) problems. IEEE Trans. on Systems, Man, and Cybernetics, 23(4): 1108\u20131129, 1993.","journal-title":"IEEE Trans. on Systems, Man, and Cybernetics"},{"issue":"3","key":"140027_CR20","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1109\/69.334864","volume":"6","author":"J. Gu","year":"1994","unstructured":"J. Gu. Global optimization for satisfiability (SAT) problems. IEEE Trans. on Knowledge and Data Engineering, 6(3): 361\u2013381, Jun 1994.","journal-title":"IEEE Trans. on Knowledge and Data Engineering"},{"key":"140027_CR21","unstructured":"J. Gu. Constraint-Based Search. Cambridge University Press, New York, to appear."},{"key":"140027_CR22","series-title":"Technical Report","volume-title":"Average time complexities of several local search algorithms for the satisfiability problem (sat)","author":"J. Gu","year":"1991","unstructured":"J. Gu and Q.-P. Gu. Average time complexities of several local search algorithms for the satisfiability problem (sat). Technical Report UCECE-TR-91-004, Univ. of Calgary, Canada, 1991."},{"key":"140027_CR23","volume-title":"Average time complexity of the sat1.3 algorithm","author":"J. Gu","year":"1992","unstructured":"J. Gu and Q.-P. Gu. Average time complexity of the sat1.3 algorithm. Technical report, Tech. Rep., Univ. of Calgary, Canada, 1992."},{"issue":"8","key":"140027_CR24","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1109\/34.149596","volume":"14","author":"J. Gu","year":"1992","unstructured":"J. Gu and W. Wang. A novel discrete relaxation architecture. IEEE Trans. on Pattern Analysis and Machine Intelligence, 14(8): 857\u2013865, August 1992.","journal-title":"IEEE Trans. on Pattern Analysis and Machine Intelligence"},{"key":"140027_CR25","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF02241270","volume":"44","author":"P. Hansen","year":"1990","unstructured":"P. Hansen and R. Jaumard. Algorithms for the maximum satisfiability problem. Computing, 44: 279\u2013303, 1990.","journal-title":"Computing"},{"key":"140027_CR26","doi-asserted-by":"crossref","unstructured":"M. Held and R. M. Karp. The traveling salesman problem and minimum spanning trees: Part II. {tiMathematical Programming}, 6: 62\u201388, 1971.","DOI":"10.1007\/BF01584070"},{"key":"140027_CR27","volume-title":"Adaption in Natural and Adaptive Systems","author":"J. H. Holland","year":"1975","unstructured":"J. H. Holland. Adaption in Natural and Adaptive Systems. University of Michigan Press, Ann Arbor, 1975."},{"key":"140027_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0167-6377(88)90044-2","volume":"7","author":"J. N. Hooker","year":"1988","unstructured":"J. N. Hooker. Resolution vs. cutting plane solution of inference problems: some computational results. Operations Research Letters, 7: 1\u20137, 1988.","journal-title":"Operations Research Letters"},{"key":"140027_CR29","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/BF02283686","volume":"25","author":"A. P. Kamath","year":"1990","unstructured":"A. P. Kamath, N. K. Karmarkar, K. G. Ramakrishnan, and M. G. C. Resende. Computational experience with an interior point algorithm on the satisfiability problem. Annals of Operations Research, 25: 43\u201358, 1990.","journal-title":"Annals of Operations Research"},{"key":"140027_CR30","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01581082","volume":"57","author":"A. P. Kamath","year":"1992","unstructured":"A. P. Kamath, N. K. Karmarkar, K. G. Ramakrishnan, and M. G. C. Resende. A continuous approach to inductive inference. Mathematical Programming, 57: 215\u2013238, 1992.","journal-title":"Mathematical Programming"},{"issue":"4598","key":"140027_CR31","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S. Kirkpatrick Jr.","year":"1983","unstructured":"S. Kirkpatrick, Jr. C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598): 671\u2013680, 1983.","journal-title":"Science"},{"key":"140027_CR32","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/BF02060483","volume":"40","author":"J. Klincewicz","year":"1992","unstructured":"J. Klincewicz. Avoiding local optima in the p-hub location problem using tabu search and GRASP. Annals of Operations Research, (40): 283\u2013302, 1992.","journal-title":"Annals of Operations Research"},{"key":"140027_CR33","unstructured":"D. G. Luenberger. Linear and Nonlinear Programming. Addison-Wesley Publishing Company, 1984."},{"key":"140027_CR34","doi-asserted-by":"crossref","unstructured":"Z. Michalewicz. Genetic Algorithms + Data Structure = Evolution Programs. Springer-Verlag, 1994.","DOI":"10.1007\/978-3-662-07418-3"},{"key":"140027_CR35","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0004-3702(92)90007-K","volume":"58","author":"S. Minton","year":"1992","unstructured":"S. Minton, M. D. Johnson, A. B. Philips, and P. Laird. Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence, 58: 161\u2013205, Dec 1992.","journal-title":"Artificial Intelligence"},{"key":"140027_CR36","unstructured":"D. Mitchell, B. Selman, and H. Levesque. Hard and easy distributions of SAT problems. In {tiProc. of the 10th National Conf. on Artificial Intelligence}, pages 459\u2013465, 1992."},{"key":"140027_CR37","unstructured":"P. Morris. The breakout method for escaping from local minima. In Proc. of the 11th National Conf. on Artificial Intelligence, pages 40\u201345, Washington, DC, 1993."},{"key":"140027_CR38","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0004-3702(83)80007-1","volume":"21","author":"P. W. Purdom","year":"1983","unstructured":"P. W. Purdom. Search rearrangement backtracking and polynomial average time. Artificial Intelligence, 21: 117\u2013133, 1983.","journal-title":"Artificial Intelligence"},{"key":"140027_CR39","doi-asserted-by":"crossref","unstructured":"M. G. C. Resende and T. Feo. AGRASP for satisfiability. In D. S. Johnson and M. A. Trick, editors, {tiCliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge}, volume 26, pages 499\u2013520. DIMACS Series on Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1996.","DOI":"10.1090\/dimacs\/026\/24"},{"key":"140027_CR40","doi-asserted-by":"crossref","unstructured":"M. G. C. Resende, L. S. Pitsoulis, and P. M. Pardalos. Approximate solution of weighted MAXSAT problems using GRASP. In Satisfiability Problem: Theory and Applications. DIMACS Series on Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1997.","DOI":"10.1090\/dimacs\/035\/11"},{"key":"140027_CR41","doi-asserted-by":"crossref","unstructured":"J. A. Robinson. A machine-oriented logic based on the resolution principle. J. Assoc. Comput. Mach., pages 23\u201341, 1965.","DOI":"10.1145\/321250.321253"},{"key":"140027_CR42","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1613\/jair.49","volume":"1","author":"R. Sebastiani","year":"1994","unstructured":"R. Sebastiani. Applying GSAT to non-clausal formulas. Journal of Artificial Intelligence Research, 1: 309\u2013314, 1994.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"140027_CR43","unstructured":"B. Selman, 1995. private communication."},{"key":"140027_CR44","unstructured":"B. Selman and H. Kautz. Domain-independent extensions to GSAT: Solving large structured satisfiability problems. In Proc. of the 13th Int'l Joint Conf. on Artificial Intelligence, pages 290\u2013295, 1993."},{"key":"140027_CR45","unstructured":"B. Selman, H. Kautz, and B. Cohen. Local search strategies for satisfiability testing. In Proc. of the Second DIMACS Challenge Workshop on Cliques, Coloring, and Satisfiability, Rutgers University, pages 290\u2013295, oct 1993."},{"key":"140027_CR46","unstructured":"B. Selman, H. Kautz, and B. Cohen. Noise strategies for improving local search. In Proc. of the 12th National Conf. on Artificial Intelligence, pages 337\u2013343, Seattle, WA, 1994."},{"key":"140027_CR47","unstructured":"B. Selman and H. A. Kautz. An empirical study of greedy local search for satisfiability testing. In {tiProc. of the 11th National Conf. on Artificial Intelligence}, pages 46\u201351, Washington, DC, 1993."},{"key":"140027_CR48","unstructured":"B. Selman, H. J. Levesque, and D. G. Mitchell. A new method for solving hard satisfiability problems. In Proc. of AAAI-92, pages 440\u2013446, San Jose, CA, 1992."},{"key":"140027_CR49","unstructured":"Y. Shang and B. W. Wah. Discrete lagrangian-based search for solving MAX-SAT problems. In {tiProc. Int'l Joint Conf. on Artificial Intelligence}. IJCAI, (accepted to appear) Aug. 1997."},{"key":"140027_CR50","volume-title":"Nonlinear Programming for Operations Research","author":"D. M. Simmons","year":"1975","unstructured":"D. M. Simmons. Nonlinear Programming for Operations Research. Prentice-Hall, Englewood Cliffs, NJ, 1975."},{"issue":"6","key":"140027_CR51","doi-asserted-by":"crossref","first-page":"1572","DOI":"10.1109\/21.135698","volume":"21","author":"R. Socic","year":"1991","unstructured":"R. Socic and J. Gu. Fast search algorithms for the N-queen problem. IEEE Trans. on Systems, Man, and Cybernetics, 21(6): 1572\u20131576, November 1991.","journal-title":"IEEE Trans. on Systems, Man, and Cybernetics"},{"issue":"3","key":"140027_CR52","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/101340.101343","volume":"1","author":"R. Sosi\u010d","year":"1990","unstructured":"R. Sosi\u010d and J. Gu. A polynomial time algorithm for the n-queens problem. SIGART Bulletin, 1(3): 7\u201311, October 1990.","journal-title":"SIGART Bulletin"},{"issue":"2","key":"140027_CR53","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/122319.122325","volume":"2","author":"R. Sosi\u010d","year":"1991","unstructured":"R. Sosi\u010d and J. Gu. 3,000,000 queens in less than one minute. SIGART Bulletin, 2(2): 22\u201324, April 1991.","journal-title":"SIGART Bulletin"},{"issue":"5","key":"140027_CR54","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1109\/69.317698","volume":"6","author":"R. Sosi\u010d","year":"1994","unstructured":"R. Sosi\u010d and J. Gu. Efficient local search with conflict minimization: A case study of the n-queens problem. IEEE Trans. on Knowledge and Data Engineering, 6(5): 661\u2013668, 1994.","journal-title":"IEEE Trans. on Knowledge and Data Engineering"},{"key":"140027_CR55","unstructured":"B. W. Wah, Y. Shang, and Z. Wu. Discrete lagrangian method for optimizing the design of multiplierless QMF filter banks. In Proc. Int'l Conf. on Application Specific Array Processors. IEEE, (accepted to appear) July 1997."},{"key":"140027_CR56","unstructured":"G. R. Walsh. Methods of Optimization. John Wiley and Sons, 1975."},{"issue":"7","key":"140027_CR57","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1109\/82.160169","volume":"39","author":"S. Zhang","year":"1992","unstructured":"S. Zhang and A. G. Constantinides. Lagrange programming neural networks. IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing, 39(7): 441\u2013452, 1992.","journal-title":"IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1008287028851.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1008287028851\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1008287028851.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T10:38:56Z","timestamp":1751366336000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1008287028851"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["140027"],"URL":"https:\/\/doi.org\/10.1023\/a:1008287028851","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}