{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:37:44Z","timestamp":1759667864791},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,10,1]],"date-time":"2005-10-01T00:00:00Z","timestamp":1128124800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2005,10]]},"DOI":"10.1007\/s10479-005-3449-7","type":"journal-article","created":{"date-parts":[[2005,9,15]],"date-time":"2005-09-15T22:31:07Z","timestamp":1126823467000},"page":"229-241","source":"Crossref","is-referenced-by-count":39,"title":["An Unconstrained Quadratic Binary Programming Approach to the Vertex Coloring Problem"],"prefix":"10.1007","volume":"139","author":[{"given":"Gary A.","family":"Kochenberger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fred","family":"Glover","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bahram","family":"Alidaee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cesar","family":"Rego","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3449_CR1","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1080\/00207729408928968","volume":"25","author":"B. Alidaee","year":"1994","unstructured":"Alidaee, B., G. Kochenberger, and A. Ahmadian. (1994). \u201c0-1 Quadratic Programming Approach for the Optimal Solution of Two Scheduling Problems.\u201d International Journal of Systems Science 25, 401\u2013408.","journal-title":"International Journal of Systems Science"},{"key":"3449_CR2","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1016\/S0377-2217(97)00130-6","volume":"108","author":"T.M. Alkhamis","year":"1998","unstructured":"Alkhamis, T.M., M. Hasan, and M.A. Ahmed. (1998). \u201cSimulated Annealing for the Unconstrained Binary Quadratic Pseudo-Boolean Function.\u201d European Journal of Operational Research 108, 641\u2013652.","journal-title":"European Journal of Operational Research"},{"key":"3449_CR3","unstructured":"Amini, M., B. Alidaee, and G. Kochenberger. (1999).\u201cA Scatter Search Approach to Unconstrained Quadratic Binary Programs.\u201d In Corne, Dorigo and Glover (eds.), New Methods in Optimization, McGraw-Hill, pp. 317\u2013330."},{"key":"3449_CR4","unstructured":"Beasley, J.E. (1999). \u201cHeuristic Algorithms for the Unconstrained Binary Quadratic Programming Problem.\u201d Working Paper, Imperial College."},{"key":"3449_CR5","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/0377-2217(94)90125-2","volume":"78","author":"A. Billionet","year":"1994","unstructured":"Billionet, A. and A. Sutter. (1994). \u201cMinimization of a Quadratic Pseudo-Boolean Function.\u201d European Journal of OR 78, 106\u2013115.","journal-title":"European Journal of OR"},{"issue":"1\u20133","key":"3449_CR6","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0166-218X(01)00341-9","volume":"123","author":"E. Boros","year":"2002","unstructured":"Boros, E. and P. Hammer. (2002). \u201cPseudo-Boolean Optimization.\u201d Discrete Applied Mathematics 123(1\u20133), 155\u2013225.","journal-title":"Discrete Applied Mathematics"},{"key":"3449_CR7","unstructured":"Boros, E., P. Hammer, and X. Sun. (1989). \u201cThe DDT Method for Quadratic 0-1 Minimization.\u201d RUTCOR Research Center, RRR 39\u201389."},{"key":"3449_CR8","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02022095","volume":"21","author":"E. Boros","year":"1989","unstructured":"Boros, E. and A. Prekopa. (1989). \u201cProbabilistic Bounds and Algorithms for the Maximum Satisfiability Problem.\u201d Annals of OR 21, 109\u2013126.","journal-title":"Annals of OR"},{"key":"3449_CR9","unstructured":"Bourjolly, J.M., P. Gill, G. Laporte and H. Mercure. (1994). \u201cA Quadratic 0\/1 Optimization Algorithm for the Maximum Clique and Stable Set Problems.\u201d Working paper, University of Montreal."},{"key":"3449_CR10","unstructured":"Campos, V., R. Marti, and M. Laguna. (2000). \u201cIntensification and Diversification with Elite Tabu Search Solutions for the Linear Ordering Problem.\u201d Working Paper, University of Colorado at Boulder."},{"issue":"4","key":"3449_CR11","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1287\/mnsc.41.4.704","volume":"41","author":"P. Chardaire","year":"1994","unstructured":"Chardaire, P. and A. Sutter. (1994). \u201cA Decomposition Method for Quadratic Zero-One Programming.\u201dManagement Science 41:4, 704\u2013712.","journal-title":"Management Science"},{"key":"3449_CR12","unstructured":"Chiarandini, M. and T. Stutzle. (2002). \u201cAn Application of Iterated Local Search to Graph Coloring.\u201d In D.S. Johnson, A. Mehrotra, and M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 112\u2013125."},{"key":"3449_CR13","doi-asserted-by":"crossref","unstructured":"Coudert, O. (1997). \u201cExact coloring of Real Life Graphs is Easy.\u201d In Proceedings of the 34th Design Automata Conference NY, pp. 121\u2013126.","DOI":"10.1109\/DAC.1997.597129"},{"key":"3449_CR14","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1109\/72.977273","volume":"13","author":"A. Jagota Di Blas","year":"2002","unstructured":"Di Blas, A. Jagota and R. Hughey. (2002). \u201cEnergy Function-Based Approaches to Graph Coloring.\u201d IEEE Transactions on Neural Networks 13, 81\u201391.","journal-title":"IEEE Transactions on Neural Networks"},{"key":"3449_CR15","volume-title":"Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization","author":"R. Dorne","year":"1999","unstructured":"Dorne, R. and J. Hao. (1999). \u201cTabu Search for Graph Coloring, t-Coloring and set t-Coloring.\u201d In S. Voss, S. Martello, I. Osman, and C. Roucairol (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Boston: Kluwer Academic Publisher."},{"issue":"4","key":"3449_CR16","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1023\/A:1009823419804","volume":"3","author":"P. Galinier","year":"1999","unstructured":"Galinier, P. and J. Hao. (1999). \u201cHybrid Evolutionary Algorithms for Graph Coloring.\u201d Journal of Combinatorial Optimization 3(4), 379\u2013397.","journal-title":"Journal of Combinatorial Optimization"},{"key":"3449_CR17","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1007\/BFb0120892","volume":"12","author":"G. Gallo","year":"1980","unstructured":"Gallo, G., P. Hammer, and B. Simeone. (1980). \u201cQuadratic Knapsack Problems.\u201d Mathematical Programming 12, 132\u2013149.","journal-title":"Mathematical Programming"},{"key":"3449_CR18","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":"3449_CR19","doi-asserted-by":"crossref","unstructured":"Glover, F. (1998). \u201cA Template for Scatter Search and Path Relinking.\u201d School of Business, University of Colorado, Technical Report.","DOI":"10.1007\/BFb0026589"},{"key":"3449_CR20","volume-title":"Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization","author":"F. Glover","year":"1999","unstructured":"Glover, F., G. Kochenberger, B. Alidaee and M.M. Amini. (1999). \u201cTabu with Search Critical Event Memory: An Enhanced Application for Binary Quadratic Programs.\u201d In S. Voss, S. Martello, I. Osman, and C. Roucairol (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Boston: Kluwer Academic Publisher."},{"key":"3449_CR21","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/S0377-2217(01)00209-0","volume":"137","author":"F. Glover","year":"2002","unstructured":"Glover, F., B. Alidaee, C. Rego, and G. Kochenberger. (2002). \u201cOne-Pass Heuristics for Large-Scale Unconstrained Binary Quadratic Programs.\u201d EJOR 137, 272\u2013287.","journal-title":"EJOR"},{"issue":"3","key":"3449_CR22","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1287\/mnsc.44.3.336","volume":"44","author":"F. Glover","year":"1998","unstructured":"Glover, F., G. Kochenberger, and B. Alidaee. (1998). \u201cAdaptive Memory Tabu Search for Binary Quadratic Programs.\u201d Management Science 44(3), 336\u2013345.","journal-title":"Management Science"},{"issue":"3","key":"3449_CR23","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"M. Grotschel","year":"1988","unstructured":"Grotschel, M., M. Junger, and G. Reinelt. (1988). \u201cAn Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design.\u201d Operations Research 36(3), 493\u2013513.","journal-title":"Operations Research"},{"key":"3449_CR24","unstructured":"Hammer, P., E. Boros, and X. Sun. (1998). \u201cOn Quadratic Unconstrained Binary Optimization.\u201d INFORMS National Meeting, Seattle, October."},{"key":"3449_CR25","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1016\/B978-0-12-468662-5.50019-7","volume-title":"Nonlinear Programming 4","author":"P. Hammer","year":"1981","unstructured":"Hammer, P., P. Hansen, and B. Simone. (1981). \u201cUpper Planes of Quadratic 0\/1 Functions and Stability in Graphs.\u201d In O. Mangasarian, R. Meyer, and S. Robinson (eds.), Nonlinear Programming 4, New York: Academic Press, pp. 395-414."},{"key":"3449_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-85823-9","volume-title":"Boolean Methods in Operations Research","author":"P. Hammer","year":"1968","unstructured":"Hammer, P. and S. Rudeanu. (1968). Boolean Methods in Operations Research. New York: Springer-Verlag."},{"key":"3449_CR27","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0167-5060(08)70343-1","volume":"5","author":"P.B. Hansen","year":"1979","unstructured":"Hansen, P.B. (1979). \u201cMethods of Nonlinear 0\u20131 Programming.\u201d Annals Discrete Math 5, 53\u201370.","journal-title":"Annals Discrete Math"},{"issue":"2","key":"3449_CR28","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1287\/ijoc.5.2.97","volume":"5","author":"P. Hansen","year":"1993","unstructured":"Hansen, P., B. Jaumard, and V. Mathon. (1993). \u201cConstrained Nonlinear 0\u20131 Programming.\u201d INFORMS Journal on Computing 5(2), 97\u2013119.","journal-title":"INFORMS Journal on Computing"},{"key":"3449_CR29","first-page":"291","volume":"82","author":"C. Helmberg","year":"1998","unstructured":"Helmberg, C. and F. Rendl. (1998). \u201cSolving Quadratic (0,1)-Problems by Semidefinite Programs and Cutting Planes.\u201d Mathematical Programming 82, 291\u2013315.","journal-title":"Mathematical Programming"},{"key":"3449_CR30","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1307\/mmj\/1028989917","volume":"2","author":"F. Harary","year":"1953\/54","unstructured":"Harary, F. (1953\/54). \u201cOn the Notion of Balanced of a Signed Graph.\u201d Michigan Mathematical Journal 2, 143\u2013146.","journal-title":"Michigan Mathematical Journal"},{"key":"3449_CR31","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1090\/dimacs\/055\/05","volume":"55","author":"L.D. Iasemidis","year":"2000","unstructured":"Iasemidis, L.D., D.S. Shiau, J.C. Sackellares, and P. Pardalos. (2000). \u201cTransition to Epileptic Seizures: Optimization.\u201d DIMACS Series in Discrete Math and Theoretical Computer Science 55, 55\u201373.","journal-title":"DIMACS Series in Discrete Math and Theoretical Computer Science"},{"key":"3449_CR32","unstructured":"Katayama, K., M. Tani, and H. Narihisa. (2000). \u201cSolving Large Binary Quadratic Programming Problems by an Effective Genetic Local Search Algorithm.\u201d In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'00).Morgan Kaufmann, pp. 643\u2013650."},{"key":"3449_CR33","unstructured":"Kochenberger, G., F. Glover, B. Alidaee, and C. Rego. (2002). \u201cApplications of the Unconstrained Quadratic Binary Program.\u201d University of Colorado Working Paper."},{"key":"3449_CR34","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BFb0120827","volume":"9","author":"J. Krarup","year":"1978","unstructured":"Krarup, J. and A. Pruzan. (1978). \u201cComputer Aided Layout Design.\u201d Mathematical Programming Study 9, 75\u201394.","journal-title":"Mathematical Programming Study"},{"key":"3449_CR35","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1287\/opre.18.3.454","volume":"14","author":"D.J. Laughunn","year":"1970","unstructured":"Laughunn, D.J. (1970). \u201cQuadratic Binary Programming.\u201d Operations Research 14, 454\u2013461.","journal-title":"Operations Research"},{"key":"3449_CR36","doi-asserted-by":"crossref","unstructured":"Lewandowski, G. and A. Condon. (1996). \u201cExperiments with Parallel Graph Coloring Heuristic and Applications of Graph Coloring.\u201d DIMACS Series in Discrete Mathematics and Theoretical Computer Science Providence, RI, American Mathematical Society, Vol. 26, pp. 335\u2013358.","DOI":"10.1090\/dimacs\/026\/15"},{"key":"3449_CR37","unstructured":"Lodi, A., K. Allemand, and T. M. Liebling. (1997). \u201cAn Evolutionary Heuristic for Quadratic 0\u20131 Programming.\u201d Technical Report OR-97-12, D.E.I.S., University of Bologna."},{"key":"3449_CR38","unstructured":"Mehrotra, A. and M. Trick. (1995). \u201cA Column Generation Approach for Graph Coloring.\u201d Working Paper, Carnegie Mellon University."},{"key":"3449_CR39","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1287\/mnsc.26.3.282","volume":"26","author":"R.D. McBride","year":"1980","unstructured":"McBride, R.D. and J.S. Yormack. (1980). \u201cAn Implicit Enumeration Algorithm for Quadratic Integer Programming.\u201d Management Science 26, 282\u2013296.","journal-title":"Management Science"},{"key":"3449_CR40","unstructured":"Merz, P. and B. Freisleben. (1999). \u201cGenetic Algorithms for Binary Quadratic Programming.\u201d In Proceedings of the 1999 International Genetic and Evolutionary Computation Conference (GECCO'99), Morgan Kaufmann, pp. 417\u2013424."},{"issue":"2","key":"3449_CR41","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1023\/A:1017912624016","volume":"8","author":"P. Merz","year":"2002","unstructured":"Merz, P. and B. Freisleben. (2002). \u201cGreedy and Local Search Heuristics for the Unconstrained Binary Quadratic Programming Problem.\u201d Journal of Heuristics 8(2), 197\u2013213.","journal-title":"Journal of Heuristics"},{"issue":"1\u20133","key":"3449_CR42","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/j.biosystems.2004.08.002","volume":"78","author":"P. Merz","year":"2004","unstructured":"Merz, P. and K. Katayama. (2004). \u201cMemetic Algorithms for the Unconstrained Binary Quadratic Program.\u201d Bio Systems 78(1\u20133), 99\u2013118.","journal-title":"Bio Systems"},{"key":"3449_CR43","unstructured":"Palubeckis, G. (1995). \u201cA Heuristic-Branch and Bound Algorithm for the Unconstrained Quadratic Zero-One Programming Problem.\u201d Computing 284\u2013301."},{"key":"3449_CR44","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF02247879","volume":"45","author":"P. Pardalos","year":"1990","unstructured":"Pardalos, P. and G.P. Rodgers. (1990). \u201cComputational Aspects of a Branch and Bound Algorithm for Quadratic Zero-one Programming.\u201d Computing 45, 131\u2013144.","journal-title":"Computing"},{"key":"3449_CR45","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0305-0548(92)90067-F","volume":"19","author":"P. Pardalos","year":"1992","unstructured":"Pardalos, P. and G.P. Rodgers. (1992). \u201cA Branch and Bound Algorithm for Maximum Clique problem.\u201d Computers & OR 19, 363\u2013375.","journal-title":"Computers & OR"},{"key":"3449_CR46","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/BF01098364","volume":"4","author":"P. Pardalos","year":"1994","unstructured":"Pardalos, P. and J. Xue. (1994). \u201cThe Maximum Clique Problem.\u201d The Journal of Global Optimization 4, 301\u2013328.","journal-title":"The Journal of Global Optimization"},{"key":"3449_CR47","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF01096724","volume":"4","author":"A.T. Phillips","year":"1994","unstructured":"Phillips, A.T. and J.B. Rosen. (1994). \u201cA Quadratic Assignment Formulation of the Molecular Conformation Problem.\u201d The Journal of Global Optimization 4, 229\u2013241.","journal-title":"The Journal of Global Optimization"},{"key":"3449_CR48","doi-asserted-by":"crossref","unstructured":"Rosenberg, I. (1972). \u201c0\/1 Optimization and Non-Linear Programming.\u201d Revue Francaise d'Automatique, d'Informatique et de Recherche Operationnelle (S\u2216'erie Bleue) 2, 95\u201397.","DOI":"10.1051\/ro\/197206V200951"},{"key":"3449_CR49","unstructured":"Williams, A.C. (1985). \u201cQuadratic 0-1 Programming Using the Roof Duality with Computational Results.\u201d Rutcor Research Report 8-85, Rutgers University, New Brunswick, NJ."},{"key":"3449_CR50","doi-asserted-by":"crossref","unstructured":"Witsgall, C. (1975). \u201cMathematical Methods of site Selection for Electronic System (EMS).\u201d NBS Internal Report.","DOI":"10.6028\/NBS.IR.75-737"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-005-3449-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-005-3449-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-005-3449-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,4]],"date-time":"2023-05-04T14:55:42Z","timestamp":1683212142000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-005-3449-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,10]]}},"alternative-id":["3449"],"URL":"https:\/\/doi.org\/10.1007\/s10479-005-3449-7","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10]]}}}