{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T17:53:41Z","timestamp":1775066021298,"version":"3.50.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2003,6,1]],"date-time":"2003-06-01T00:00:00Z","timestamp":1054425600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2003,6,1]],"date-time":"2003-06-01T00:00:00Z","timestamp":1054425600000},"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 Heuristics"],"published-print":{"date-parts":[[2003,6]]},"DOI":"10.1023\/a:1023721723676","type":"journal-article","created":{"date-parts":[[2003,6,6]],"date-time":"2003-06-06T18:11:05Z","timestamp":1054923065000},"page":"175-227","source":"Crossref","is-referenced-by-count":24,"title":["Tutorial on Surrogate Constraint Approaches for Optimization in Graphs"],"prefix":"10.1007","volume":"9","author":[{"given":"Fred","family":"Glover","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5123632_CR1","unstructured":"Abello, J., P.M. Pardalos, and M.G.C. Resende. (1999). \u201cOn Maximum Clique Problems in Very Large Graphs.\u201d In J. Abello and J. Vitter (eds.), External Memory Algorithms and Visualization, DIMACS Series on Discrete Mathematics and Theoretical Computer Science. American Mathematical Society 50, 199\u2013230."},{"key":"5123632_CR2","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chvatal","year":"1979","unstructured":"Chvatal, V. (1979). \u201cA Greedy Heuristic for the Set-Covering Problem,\u201d Mathematics of Operations Research 4, 233\u2013235.","journal-title":"Mathematics of Operations Research"},{"key":"5123632_CR3","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01581647","volume":"19","author":"M.F. Dyer","year":"1980","unstructured":"Dyer, M.F. (1980). \u201cCalculating Surrogate Constraints,\u201d Mathematical Programming 19, 255\u2013278.","journal-title":"Mathematical Programming"},{"key":"5123632_CR4","doi-asserted-by":"crossref","first-page":"745","DOI":"10.1007\/BFb0056916","volume":"1498","author":"R. Dorne","year":"1998","unstructured":"Dorne, R. and J.K. Hao. (1998). \u201cA New Genetic Local Search Algorithm for Graph Coloring,\u201d Lecture Notes in Computer Science 1498. Springer-Verlag, pp. 745\u2013754.","journal-title":"Lecture Notes in Computer Science"},{"issue":"5","key":"5123632_CR5","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1287\/opre.42.5.860","volume":"42","author":"Feo","year":"1994","unstructured":"Feo, Thomas A., Mauricio G.C., Resende, and Stuart H. Smith. (1994). \u201cA Greedy Randomized Adaptive Search Procedure for Maximum Independent Set,\u201d Operations Research 42(5), 860\u2013878.","journal-title":"Operations Research"},{"key":"5123632_CR6","volume-title":"Des Bornes Duales Robustes pour le Sac \u00e1 Dos Bidimensionnel en Variables 0\u20131.ROADF'2000","author":"A. Fr\u00e9ville","year":"2000","unstructured":"Fr\u00e9ville, A. and S. Hanafi. (2000). Des Bornes Duales Robustes pour le Sac \u00e1 Dos Bidimensionnel en Variables 0\u20131.ROADF'2000. Nantes, France."},{"key":"5123632_CR7","volume-title":"Graphs and Optimization Colloquium","author":"A. Fr\u00e9ville","year":"1992","unstructured":"Fr\u00e9ville, A. and G. Plateau. (1992). \u201cAn Implicit Enumeration Code for the Solution of the 0\u20131 Bidimensional Knapsack Problem Based on Surrogate Duality,\u201d Graphs and Optimization Colloquium. Grimentz, Switzerland."},{"key":"5123632_CR8","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1016\/0377-2217(93)90197-U","volume":"68","author":"A. Fr\u00e9ville","year":"1993","unstructured":"Fr\u00e9ville, A. and G. Plateau. (1993). \u201cAn Exact Search for the Solution of the Surrogate Dual of the 0\u20131 Bidimensional Knapsack Problem,\u201d European Journal of Operational Research 68, 413\u2013421.","journal-title":"European Journal of Operational Research"},{"key":"5123632_CR9","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02243141","volume":"42","author":"C. Friden","year":"1989","unstructured":"Friden, C., A. Hertz, and D. de Werra. (1989). \u201cStabulus: A Technique for Finding Stable Sets in Large Graphs with Tabu Search,\u201d Computing 42, 35\u201344.","journal-title":"Computing"},{"key":"5123632_CR10","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/0305-0548(90)90048-C","volume":"155","author":"C. Friden","year":"1990","unstructured":"Friden, C., A. Hertz, and D. de Werra. (1990). \u201cTabaris: An Exact Algorithm Based on Tabu Search for Finding a Maximum Independent Set in a Graph,\u201d Computers & Operations Research 155, 437\u2013445.","journal-title":"Computers & Operations Research"},{"issue":"4","key":"5123632_CR11","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1023\/A:1009823419804","volume":"3","author":"P. Galinier","year":"1999","unstructured":"Galinier, P. and J.K. Hao. (1999). \u201cHybrid Evolutionary Algorithms for Graph Coloring,\u201d Journal of Combinatorial Optimization 3(4), 379\u2013397.","journal-title":"Journal of Combinatorial Optimization"},{"key":"5123632_CR12","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BF02591863","volume":"31","author":"B. Gavish","year":"1985","unstructured":"Gavish, B. and H. Pirkul. (1985). \u201cEfficient Algorithms for Solving Multiconstraint Zero-one Knapsack Problems to Optimality,\u201d Mathematical Programming 31, 78\u2013105.","journal-title":"Mathematical Programming"},{"issue":"2","key":"5123632_CR13","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1080\/02522667.1991.10699064","volume":"12","author":"B. Gavish","year":"1991","unstructured":"Gavish, B., F. Glover, and H. Pirkul. (1991). \u201cSurrogate Constraints in Integer Programming,\u201d Journal of Infor-mation and Optimization Sciences 12(2), 219\u2013228.","journal-title":"Journal of Infor-mation and Optimization Sciences"},{"issue":"6","key":"5123632_CR14","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1287\/opre.13.6.879","volume":"13","author":"F. Glover","year":"1965","unstructured":"Glover, F. (1965). \u201cA Multiphase-Dual Algorithm for the Zero-One Integer Programming Problems,\u201d Operations Research 13(6), 879\u2013893.","journal-title":"Operations Research"},{"issue":"4","key":"5123632_CR15","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1287\/opre.16.4.741","volume":"16","author":"F. Glover","year":"1968","unstructured":"Glover, F. (1968). \u201cSurrogate Constraints,\u201d Operations Research 16(4), 741\u2013749.","journal-title":"Operations Research"},{"issue":"9","key":"5123632_CR16","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1287\/mnsc.17.9.568","volume":"17","author":"F. Glover","year":"1971","unstructured":"Glover, F. (1971). \u201cFlows in Arborescences,\u201d Management Science 17(9), 568\u2013586.","journal-title":"Management Science"},{"issue":"3","key":"5123632_CR17","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1287\/opre.23.3.434","volume":"23","author":"F. Glover","year":"1975","unstructured":"Glover, F. (1975). \u201cSurrogate Constraint Duality in Mathematical Programming,\u201d Operations Research 23(3), 434\u2013451.","journal-title":"Operations Research"},{"issue":"1","key":"5123632_CR18","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1111\/j.1540-5915.1977.tb01074.x","volume":"8","author":"F. Glover","year":"1977","unstructured":"Glover, F. (1977). \u201cHeuristics for Integer Programming Using Surrogate Constraints,\u201d Decision Sciences 8(1), 156\u2013166.","journal-title":"Decision Sciences"},{"key":"5123632_CR19","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0166-218X(94)90211-9","volume":"49","author":"F. Glover","year":"1994","unstructured":"Glover, F. (1994). \u201cTabu Search for Nonlinear and Parametric Optimization (with Links to Genetic Algorithms),\u201d Discrete Applied Mathematics 49, 231\u2013255.","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"5123632_CR20","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/BF01580728","volume":"40","author":"F. Glover","year":"1988","unstructured":"Glover, F. and D. Klingman. (1988). \u201cLayering Strategies for Creating Exploitable Structure in Linear and Integer Programs,\u201d Mathematical Programming 40(2), 165\u2013182.","journal-title":"Mathematical Programming"},{"key":"5123632_CR21","unstructured":"Glover, F. and M. Laguna. (1993). \u201cTabu Search.\u201d In C. Reeves (ed.), Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientific Publishing, pp. 71\u2013140."},{"key":"5123632_CR22","doi-asserted-by":"crossref","unstructured":"Glover, F. and M. Laguna. (1997). Tabu Search. Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4615-6089-0"},{"key":"5123632_CR23","doi-asserted-by":"crossref","unstructured":"Glover, F. and G. Kochenberger. (1996). \u201cCritical Event Tabu Search for Multidimensional Knapsack Problems.\u201d J.H. Osman and J.P. Kelly (eds.), Meta-Heuristics: Theory & Applications. Kluwer Academic Publishers, pp. 407\u2013427.","DOI":"10.1007\/978-1-4613-1361-8_25"},{"issue":"2","key":"5123632_CR24","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1023\/A:1008621204567","volume":"8","author":"F. Glover","year":"1997","unstructured":"Glover, F., H.D. Sherali, and Y. Lee. (1997). \u201cGenerating Cuts from Surrogate Constraint Analysis for Zero-One and Multiple Choice Programming,\u201d Computational Optimization and Applications 8(2), 151\u2013172.","journal-title":"Computational Optimization and Applications"},{"key":"5123632_CR25","doi-asserted-by":"crossref","unstructured":"Glover, F. (2000). \u201cMulti-Start and Strategic Oscillation Methods\u2014Principles to Exploit Adaptive Memory.\u201d M. Laguna and J.L. Gonzales Velarde (eds.), Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research. Kluwer Academic Publishers, pp. 1\u201324.","DOI":"10.1007\/978-1-4615-4567-5_1"},{"key":"5123632_CR26","doi-asserted-by":"crossref","first-page":"924","DOI":"10.1287\/opre.18.5.924","volume":"18","author":"H.J. Greenberg","year":"1970","unstructured":"Greenberg, H.J. and W.P. Pierskalla. (1970). \u201cSurrogate Mathematical Programs,\u201d Operations Research 18, 924\u2013939.","journal-title":"Operations Research"},{"key":"5123632_CR27","first-page":"437","volume":"15","author":"H.J. Greenberg","year":"1973","unstructured":"Greenberg, H.J. and W.P. Pierskalla. (1973). \u201cQuasi-Conjugate Functions and Surrogate Duality.\u201d Cahiers due Centre d'Etudes de Recherche Operationelle 15, 437\u2013448.","journal-title":"Cahiers due Centre d'Etudes de Recherche Operationelle"},{"key":"5123632_CR28","unstructured":"Hanafi S. (1993). \u201cContribution \u00e1 la R\u00e9solution de Probl' emes Duaux de Grande Taille en Optimisation Combinatoire,\u201d Ph.D. thesis, Universit\u00e9 de Valenciennes et du Hainaut-Cambr\u00e9sis, France."},{"key":"5123632_CR29","unstructured":"Hanafi, S. and A. Fr\u00e9ville. (2001). \u201cR\u00e9solution du Dual Composite du Sac \u00e1 Dos Bidimensionnel en variables 0\u20131 par une m\u00e9thode de Branch-and-Bound,\u201d Francoro III Conference, Quebec, Canada."},{"key":"5123632_CR30","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1090\/dimacs\/026\/09","volume":"26","author":"S. Homer","year":"1996","unstructured":"Homer, S. and M. Peinado. (1996). \u201cExperiments with Polynomial-time CLIQUE Approximation Algorithms on Very Large Graphs,\u201d DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26, 147\u2013155.","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"5123632_CR31","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S. (1974). \u201cApproximation Algorithms for Combinatorial Problems,\u201d Journal of Computer and System Sciences 9, 256\u2013278.","journal-title":"Journal of Computer and System Sciences"},{"key":"5123632_CR32","doi-asserted-by":"crossref","unstructured":"Johnson, D.S. and M.A. Trick. (eds.) (1996). Clique, Coloring and Satisfiability, Second Implementation Challenge. DIMACS, AMS.","DOI":"10.1090\/dimacs\/026"},{"key":"5123632_CR33","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1016\/S0377-2217(97)00011-8","volume":"104","author":"A. Joseph","year":"1998","unstructured":"Joseph, A., S. Gass, and N. Bryson. (1998). \u201cAn Objective Hyperplane Procedure for Solving the General All-Integer Linear Programming (ILP) Problem,\u201d European Journal of Operational Research 104, 601\u2013614.","journal-title":"European Journal of Operational Research"},{"key":"5123632_CR34","first-page":"141","volume-title":"Quantitative Planning and Control","author":"D. Klingman","year":"1979","unstructured":"Klingman, D. and D. Karney. (1979). \u201cA Study of Alternative Relaxation Approaches for a Manpower Planning Problem.\u201d Ijiri and Whinston (eds.), Quantitative Planning and Control. Academic Press, Inc., NY, pp. 141\u2013164."},{"issue":"1","key":"5123632_CR35","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1111\/j.1540-5915.1974.tb00593.x","volume":"5","author":"G.A. Kochenberger","year":"1974","unstructured":"Kochenberger, G.A., B.A. McCarl, and F.P. Wyman. (1974). \u201cA Heuristic for General Integer Programming,\u201d Decision Sciences 5(1), 36\u201344.","journal-title":"Decision Sciences"},{"key":"5123632_CR36","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1090\/dimacs\/035\/14","volume":"35","author":"A. L\u00d8kketangen","year":"1997","unstructured":"L\u00d8kketangen, A. and F. Glover. (1997). \u201cSurrogate Constraint Analysis\u2014New Heuristics and Learning Schemes for Satisfiability Problems,\u201d DIMACS Series in Discrete Mathematics and Theoretical Computer Science 35, 537\u2013572.","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"5123632_CR37","doi-asserted-by":"crossref","unstructured":"Osorio, M.A., F. Glover, and P. Hammer. (2002). \u201cSurrogate Constraint Analysis for Improved Multidimensional Knapsack Solutions,\u201d Discrete Applied Mathematics.","DOI":"10.1023\/A:1021513321301"},{"key":"5123632_CR38","doi-asserted-by":"crossref","unstructured":"Ouyang, M., M. Toulouse, K. Thulasiraman, F. Glover, and J.S. Deogun. (2000a). \u201cMultilevel Cooperative Search for the Circuit\/Hypergraph Partitioning Problem,\u201d IEEE Transactions on Computer-Aided Design.","DOI":"10.1145\/332357.332399"},{"key":"5123632_CR39","doi-asserted-by":"crossref","unstructured":"Ouyang, M., M. Toulouse, K. Thulasiraman, F. Glover, and J.S. Deogun. (2000b). \u201cMulti-Level Cooperative Search: Application to the Netlist\/Hypergraph Partitioning Problem,\u201d International Symposium on Physical Design. ACM Press, pp. 192\u2013198.","DOI":"10.1145\/332357.332399"},{"key":"5123632_CR40","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF01580121","volume":"5","author":"M.W. Padberg","year":"1973","unstructured":"Padberg, M.W. (1973). \u201cOn the Facial Structure of Set Packing Polyhedra,\u201d Mathematical Programming 5, 199\u2013215.","journal-title":"Mathematical Programming"},{"issue":"3","key":"5123632_CR41","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/BF01098364","volume":"4","author":"P. Pardalos","year":"1994","unstructured":"Pardalos, P. and J. Xue. (1994). \u201cThe Maximum Clique Problem,\u201d J.of Global Optimization 4(3), 286\u2013301.","journal-title":"J. of Global Optimization"},{"key":"5123632_CR42","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1145\/293686.293690","volume":"24","author":"M.G.C. Resende","year":"1998","unstructured":"Resende, M.G.C., T.A. Feo, and S.H. Smith. (1998). \u201cAlgorithm 787: Fortran Subroutines for Approximate Solution of Maximum Independent Set Problems Using GRASP,\u201d ACMTransactions on Mathematical Software 24, 386\u2013394.","journal-title":"ACMTransactions on Mathematical Software"},{"key":"5123632_CR43","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/3-540-48311-X_75","volume":"1685","author":"M. Toulouse","year":"1999","unstructured":"Toulouse, M., K. Thulasiram, and F. Glover. (1999). \u201cMulti-Level Cooperative Search,\u201d Lecture Notes in Computer Science, Vol. 1685, Springer-Verlag, pp. 533\u2013542.","journal-title":"Lecture Notes in Computer Science"},{"issue":"1","key":"5123632_CR44","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1023\/A:1022601301102","volume":"98","author":"G. Yu","year":"1998","unstructured":"Yu, G. (1998). \u201cMin-Max Optimization of Several Classical Discrete Optimization Poblems,\u201d O Journal of Optimization Theory and Applications 98(1), 221\u2013242.","journal-title":"O Journal of Optimization Theory and Applications"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1023721723676.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1023721723676\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1023721723676.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T10:59:35Z","timestamp":1747652375000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1023721723676"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,6]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,6]]}},"alternative-id":["5123632"],"URL":"https:\/\/doi.org\/10.1023\/a:1023721723676","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,6]]}}}