{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T09:08:40Z","timestamp":1743152920790,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":54,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9781441913050"},{"type":"electronic","value":"9781441913067"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-1-4419-1306-7_3","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T18:32:39Z","timestamp":1252953159000},"page":"71-102","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["MetaBoosting: Enhancing Integer Programming Techniques by Metaheuristics"],"prefix":"10.1007","author":[{"given":"Jakob","family":"Puchinger","sequence":"first","affiliation":[]},{"given":"G\u00fcnther R.","family":"Raidl","sequence":"additional","affiliation":[]},{"given":"Sandro","family":"Pirkwieser","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,9,1]]},"reference":[{"issue":"2","key":"3_CR1","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1016\/S0377-2217(97)00290-7","volume":"106","author":"P. Augerat","year":"1999","unstructured":"P. Augerat, J.M. Belenguer, E. Benavent, A. Corberan, and D. Naddef. Separating capacity constraints in the CVRP using tabu search. European Journal of Operational Research, 106(2):546\u2013557, 1999.","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"3_CR2","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1287\/opre.13.4.517","volume":"13","author":"E. Balas","year":"1965","unstructured":"E. Balas. An additive algorithm for solving linear programs with zero-one variables. Operations Research, 13(4):517\u2013549, 1965.","journal-title":"Operations Research"},{"issue":"1","key":"3_CR3","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1287\/mnsc.26.1.86","volume":"26","author":"E. Balas","year":"1980","unstructured":"E. Balas and C.H. Martin. Pivot and complement \u2013 a heuristic for 0\u20131 programming. Management Science, 26(1):86\u201396, 1980.","journal-title":"Management Science"},{"issue":"3","key":"3_CR4","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/s101070050002","volume":"87","author":"F. Barahona","year":"2000","unstructured":"F. Barahona and R. Anbil. The volume algorithm: Producing primal solutions with a subgradient method. Mathematical Programming, Series A, 87(3):385\u2013399, 2000.","journal-title":"Mathematical Programming, Series A"},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.disopt.2006.10.001","volume":"4","author":"L. Bertaccoa","year":"2007","unstructured":"L. Bertaccoa, M. Fischetti, and A. Lodi. A feasibility pump heuristic for general mixed-integer problems. Discrete Optimization, 4:63\u201376, 2007.","journal-title":"Discrete Optimization"},{"key":"3_CR6","unstructured":"D. Bertsimas and J.N. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1997."},{"issue":"10","key":"3_CR7","doi-asserted-by":"publisher","first-page":"2972","DOI":"10.1016\/j.cor.2005.02.029","volume":"33","author":"A. Chabrier","year":"2006","unstructured":"A. Chabrier. Vehicle routing problem with elementary shortest path based column generation. Computers & Operations Research, 33(10):2972\u20132990, 2006.","journal-title":"Computers & Operations Research"},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1057\/palgrave.jors.2601163","volume":"52","author":"J.-F. Cordeau","year":"2001","unstructured":"J.-F. Cordeau, G. Laporte, and A. Mercier. A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52:928\u2013936, 2001.","journal-title":"Journal of the Operational Research Society"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10107-004-0518-7","volume":"102","author":"E. Danna","year":"2005","unstructured":"E. Danna, E. Rothberg, and C. Le Pape. Exploring relaxation induced neighborhoods to improve MIP solutions. Mathematical Programming, Series A, 102:71\u201390, 2005.","journal-title":"Mathematical Programming, Series A"},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1287\/opre.2.4.393","volume":"2","author":"G.B. Dantzig","year":"1954","unstructured":"G.B. Dantzig, D.R. Fulkerson, and S.M. Johnson. Solution of a large scale traveling salesman problem. Operations Research, 2:393\u2013410, 1954.","journal-title":"Operations Research"},{"issue":"1","key":"3_CR11","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1287\/opre.8.1.101","volume":"8","author":"G.B. Dantzig","year":"1960","unstructured":"G.B. Dantzig and P. Wolfe. Decomposition principle for linear programs. Operations Research, 8(1):101\u2013111, 1960.","journal-title":"Operations Research"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"J. Denzinger and T. Offermann. On cooperation between evolutionary algorithms and other search paradigms. In Proceedings of the 1999 Congress on Evolutionary Computation, volume 3, pages 2317\u20132324. IEEE Press, 1999.","DOI":"10.1109\/CEC.1999.785563"},{"issue":"1-3","key":"3_CR13","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/S0012-365X(98)00213-1","volume":"194","author":"O. du Merle","year":"1999","unstructured":"O. du Merle, D. Villeneuve, J. Desrosiers, and P. Hansen. Stabilized column generation. Discrete Mathematics, 194(1-3):229\u2013237, 1999.","journal-title":"Discrete Mathematics"},{"issue":"3","key":"3_CR14","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1002\/net.20033","volume":"44","author":"D. Feillet","year":"2004","unstructured":"D. Feillet, P. Dejax, M. Gendreau, and C. Gueguen. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks, 44(3):216\u2013229, 2004.","journal-title":"Networks"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01096763","volume":"6","author":"T.A. Feo","year":"1995","unstructured":"T.A. Feo and M.G.C. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109\u2013133, 1995.","journal-title":"Journal of Global Optimization"},{"key":"3_CR16","unstructured":"G. Ribeiro Filho and L.A. Nogueira Lorena. Constructive genetic algorithm and column generation: an application to graph coloring. In L.P. Chuen, editor, Proceedings of the Fifth Conference of the Association of Asian-Pacific Operations Research Societies within IFORS, 2000."},{"issue":"1","key":"3_CR17","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s10107-004-0570-3","volume":"104","author":"M. Fischetti","year":"2005","unstructured":"M. Fischetti, F. Glover, and A. Lodi. The feasibility pump. Mathematical Programming, 104(1):91\u2013104, 2005.","journal-title":"Mathematical Programming"},{"issue":"2","key":"3_CR18","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/net.20017","volume":"44","author":"M. Fischetti","year":"2004","unstructured":"M. Fischetti, C. Polo, and M. Scantamburlo. Local branching heuristic for mixed-integer programs with 2-level variables, with an application to a telecommunication network design problem. Networks, 44(2):61\u201372, 2004.","journal-title":"Networks"},{"key":"3_CR19","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s10107-003-0395-5","volume":"98","author":"M. Fischetti","year":"2003","unstructured":"M. Fischetti and A. Lodi. Local branching. Mathematical Programming, Series B, 98:23\u201347, 2003.","journal-title":"Mathematical Programming, Series B"},{"issue":"1","key":"3_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/mnsc.27.1.1","volume":"27","author":"M.L. Fisher","year":"1981","unstructured":"M.L. Fisher. The Lagrangian relaxation method for solving integer programming problems. Management Science, 27(1):1\u201318, 1981.","journal-title":"Management Science"},{"issue":"1","key":"3_CR21","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s10479-005-3447-9","volume":"139","author":"A. Frangioni","year":"2005","unstructured":"A. Frangioni. About Lagrangian methods in integer optimization. Annals of Operations Research, 139(1):163\u2013193, 2005.","journal-title":"Annals of Operations Research"},{"key":"3_CR22","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1023\/A:1011921025322","volume":"7","author":"A.P. French","year":"2001","unstructured":"A.P. French, A.C. Robinson, and J.M. Wilson. Using a hybrid genetic algorithm\/branch and bound approach to solve feasibility and optimization integer programming problems. Journal of Heuristics, 7:551\u2013564, 2001.","journal-title":"Journal of Heuristics"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"S. Ghosh. DINS, a MIP improvement heuristic. In M. Fischetti and D.P. Williamson, editors, Integer Programming and Combinatorial Optimization: 12th International IPCO Conference, Proceedings, volume 4513 of Lecture Notes in Computer Science, pages 310\u2013323. Springer, 2007.","DOI":"10.1007\/978-3-540-72792-7_24"},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1287\/opre.9.6.849","volume":"9","author":"P.C. Gilmore","year":"1961","unstructured":"P.C. Gilmore and R.E. Gomory. A linear programming approach to the cutting stock problem. Operations Research, 9:849\u2013859, 1961.","journal-title":"Operations Research"},{"issue":"3","key":"3_CR25","first-page":"653","volume":"39","author":"F. Glover","year":"2000","unstructured":"F. Glover, M. Laguna, and R. Mart\u00ed. Fundamentals of scatter search and path relinking. Control and Cybernetics, 39(3):653\u2013684, 2000.","journal-title":"Control and Cybernetics"},{"issue":"4","key":"3_CR26","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1287\/opre.16.4.741","volume":"16","author":"F. Glover","year":"1968","unstructured":"F. Glover. Surrogate constraints. Operations Research, 16(4):741\u2013749, 1968.","journal-title":"Operations Research"},{"issue":"10","key":"3_CR27","doi-asserted-by":"publisher","first-page":"3034","DOI":"10.1016\/j.cor.2005.02.033","volume":"33","author":"P. Hansen","year":"2006","unstructured":"P. Hansen, N. Mladenovi\u0107, and D. Urosevi\u0107. Variable neighborhood search and local branching. Computers & Operations Research, 33(10):3034\u20133045, 2006.","journal-title":"Computers & Operations Research"},{"issue":"5","key":"3_CR28","doi-asserted-by":"publisher","first-page":"1274","DOI":"10.1016\/j.cor.2004.09.017","volume":"33","author":"M. Haouari","year":"2006","unstructured":"M. Haouari and J.C. Siala. A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem. Computers & Operations Research, 33(5):1274\u20131288, 2006.","journal-title":"Computers & Operations Research"},{"key":"3_CR29","volume-title":"Weight-constrained minimal spanning tree problem. Master\u2019s thesis","author":"S.T. Henn","year":"2007","unstructured":"S.T. Henn. Weight-constrained minimal spanning tree problem. Master\u2019s thesis, University of Kaiserslautern, Department of Mathematics, May 2007."},{"issue":"4","key":"3_CR30","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1287\/opre.17.4.600","volume":"17","author":"F.S. Hillier","year":"1969","unstructured":"F.S. Hillier. Efficient heuristic procedures for integer linear programming with an interior. Operations Research, 17(4):600\u2013637, 1969.","journal-title":"Operations Research"},{"key":"3_CR31","doi-asserted-by":"publisher","unstructured":"S. Irnich and G. Desaulniers. Shortest path problems with resource constraints. In G. Desaulniers, J. Desrosiers, and M.M. Solomon, editors, Column Generation, chapter 2, pages 33\u201365. Springer, 2005.","DOI":"10.1007\/978-1-4419-1306-7_2"},{"key":"3_CR32","unstructured":"J. Larsen. Parallelization of the Vehicle Routing Problem with Time Windows. PhD thesis, Technical University of Denmark, 1999."},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"M. Leitner and G.R. Raidl. Lagrangian decomposition, metaheuristics, and hybrid approaches for the design of the last mile in fiber optic networks. In M.J. Blesa, C. Blum, C. Cotta, A.J. Fern\u00e1ndez, J.E. Gallardo, A. Roli, and M. Sampels, editors, Hybrid Metaheuristics 2008, volume 5296 of Lecture Notes in Computer Science, pages 158\u2013174. Springer, 2008.","DOI":"10.1007\/978-3-540-88439-2_12"},{"key":"3_CR34","unstructured":"H.R. Lourenco, O. Martin, and T. St\u00fctzle. Iterated local search. In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, pages 321\u2013353. Kluwer Academic Publishers, 2003."},{"issue":"6","key":"3_CR35","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1287\/opre.1050.0234","volume":"53","author":"M.E. L\u00fcbbecke","year":"2005","unstructured":"M.E. L\u00fcbbecke and J. Desrosiers. Selected topics in column generation. Operations Research, 53(6):1007\u20131023, 2005.","journal-title":"Operations Research"},{"key":"3_CR36","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1287\/mnsc.45.3.414","volume":"45","author":"S. Martello","year":"1999","unstructured":"S. Martello, D. Pisinger, and P. Toth. Dynamic programming and strong bounds for the 0\u20131 knapsack problem. Management Science, 45:414\u2013424, 1999.","journal-title":"Management Science"},{"key":"3_CR37","doi-asserted-by":"crossref","unstructured":"G.L. Nemhauser and L.A. Wolsey. Integer and Combinatorial Optimization. John Wiley & Sons, 1988.","DOI":"10.1002\/9781118627372"},{"key":"3_CR38","first-page":"87","volume-title":"International Conference on Constraint Programming, Proceedings of the Workshop on Cooperative Solvers in Constraint Programming","author":"C. Oliva","year":"2001","unstructured":"C. Oliva, P. Michelon, and C. Artigues. Constraint and linear programming: Using reduced costs for solving the zero\/one multiple knapsack problem. In International Conference on Constraint Programming, Proceedings of the Workshop on Cooperative Solvers in Constraint Programming, pages 87\u201398, Paphos, Greece, 2001."},{"key":"3_CR39","volume-title":"Proceedings of the 9th EU\/MEeting on Metaheuristics for Logistics and Vehicle Routing","author":"S. Pirkwieser","year":"2008","unstructured":"S. Pirkwieser and G.R. Raidl. variable neighborhood search for the periodic vehicle routing problem with time windows. In C. Prodhon, R. Wolfler-Calvo, N. Labadi, and C. Prins, editors, Proceedings of the 9th EU\/MEeting on Metaheuristics for Logistics and Vehicle Routing, Troyes, France, 2008."},{"key":"3_CR40","doi-asserted-by":"crossref","unstructured":"S. Pirkwieser, G.R. Raidl, and J. Puchinger. A Lagrangian decomposition\/evolutionary algorithm hybrid for the knapsack constrained maximum spanning tree problem. In C. Cotta and J. van Hemert, editors, Recent Advances in Evolutionary Computation for Combinatorial Optimization, volume 153 of Studies in Computational Intelligence, pages 69\u201385. Springer, 2008.","DOI":"10.1007\/978-3-540-70807-0_5"},{"key":"3_CR41","doi-asserted-by":"crossref","unstructured":"J. Puchinger and G.R. Raidl. An evolutionary algorithm for column generation in integer programming: an effective approach for 2D bin packing. In In X. Yao, E.K. Burke, J.A. Lozano, J. Smith, J.J. Merelo-Guervos, J.A. Bullinaria, J.E. Rowe, P. Tino, A. Kaban, and H.-P. Schwefel, editors, Parallel Problem Solving from Nature \u2013 PPSN VIII, volume 3242 of Lecture Notes in Computer Science, pages 642\u2013651. Springer, 2004.","DOI":"10.1007\/978-3-540-30217-9_65"},{"key":"3_CR42","doi-asserted-by":"crossref","unstructured":"J. Puchinger and G.R. Raidl. Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification. In J. Mira and J.R. \u00c1lvarez, editors, Proceedings of the First International Work-Conference on the Interplay Between Natural and Artificial Computation, Part II, volume 3562 of Lecture Notes in Computer Science, pages 41\u201353. Springer, 2005.","DOI":"10.1007\/11499305_5"},{"key":"3_CR43","doi-asserted-by":"publisher","first-page":"1304","DOI":"10.1016\/j.ejor.2005.11.064","volume":"183","author":"J. Puchinger","year":"2007","unstructured":"J. Puchinger and G.R. Raidl. Models and algorithms for three-stage two-dimensional bin packing. European Journal of Operational Research, 183:1304\u20131327, 2007.","journal-title":"European Journal of Operational Research"},{"key":"3_CR44","unstructured":"J. Puchinger, G.R. Raidl, and M. Gruber. Cooperating memetic and branch-and-cut algorithms for solving the multidimensional knapsack problem. In Proceedings of the 6th Metaheuristics International Conference, pages 775\u2013780, Vienna, Austria, 2005."},{"issue":"3","key":"3_CR45","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1109\/TEVC.2002.807275","volume":"7","author":"G.R. Raidl","year":"2003","unstructured":"G.R. Raidl and B.A. Julstrom. dge sets: an effective evolutionary coding of spanning trees. IEEE Transactions on Evolutionary Computation, 7(3):225\u2013239, 2003.","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"3_CR46","unstructured":"W. Rei, J.-F. Cordeau, M. Gendreau, and P. Soriano. Accelerating Benders decomposition by local branching. INFORMS Journal on Computing, in press."},{"issue":"4","key":"3_CR47","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1287\/ijoc.1060.0189","volume":"19","author":"E. Rothberg","year":"2007","unstructured":"E. Rothberg. An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS Journal on Computing, 19(4):534\u2013541, 2007.","journal-title":"INFORMS Journal on Computing"},{"key":"3_CR48","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1287\/ijoc.4.2.146","volume":"4","author":"M.W.P. Savelsbergh","year":"1992","unstructured":"M.W.P. Savelsbergh. The vehicle routing problem with time windows: Minimizing route duration. ORSA Journal on Computing, 4:146\u2013154, 1992.","journal-title":"ORSA Journal on Computing"},{"key":"3_CR49","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1023\/A:1009669824615","volume":"4","author":"S. Talukdar","year":"1998","unstructured":"S. Talukdar, L. Baeretzen, A. Gove, and P. de Souza. Asynchronous teams: Cooperation schemes for autonomous agents. Journal of Heuristics, 4:295\u2013321, 1998.","journal-title":"Journal of Heuristics"},{"key":"3_CR50","unstructured":"M. Vasquez and J.-K. Hao. A hybrid approach for the 0\u20131 multidimensional knapsack problem. In B. Nebel, editor, Proceedings of the 17th International Joint Conference on Artificial Intelligence, pages 328\u2013333. Morgan Kaufman, 2001."},{"issue":"1","key":"3_CR51","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.ejor.2004.01.024","volume":"165","author":"M. Vasquez","year":"2005","unstructured":"M. Vasquez and Y. Vimont. Improved results on the 0\u20131 multidimensional knapsack problem. European Journal of Operational Research, 165(1):70\u201381, 2005.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"3_CR52","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s10878-007-9074-4","volume":"15","author":"Y. Vimont","year":"2008","unstructured":"Y. Vimont, S. Boussier, and M. Vasquez. Reduced costs propagation in an efficient implicit enumeration for the 0\u20131 multidimensional knapsack problem. Journal of Combinatorial Optimization, 15(2):165\u2013178, 2008.","journal-title":"Journal of Combinatorial Optimization"},{"key":"3_CR53","unstructured":"L.A. Wolsey. Integer Programming. Wiley-Interscience, 1998."},{"issue":"1","key":"3_CR54","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1080\/00207160412331290667","volume":"82","author":"T. Yamada","year":"2005","unstructured":"T. Yamada, K. Watanabe, and S. Katakoa. Algorithms to solve the knapsack constrained maximum spanning tree problem. International Journal of Computer Mathematics, 82(1):23\u201334, 2005.","journal-title":"International Journal of Computer Mathematics"}],"container-title":["Annals of Information Systems","Matheuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4419-1306-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T04:17:27Z","timestamp":1739333847000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-1-4419-1306-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9781441913050","9781441913067"],"references-count":54,"URL":"https:\/\/doi.org\/10.1007\/978-1-4419-1306-7_3","relation":{},"ISSN":["1934-3221","1934-3213"],"issn-type":[{"type":"print","value":"1934-3221"},{"type":"electronic","value":"1934-3213"}],"subject":[],"published":{"date-parts":[[2009]]},"assertion":[{"value":"1 September 2009","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}