Skip to Main content Skip to Navigation
New interface
Conference papers

Recent results for column generation based diving heuristics

Ruslan Sadykov 1, 2 François Vanderbeck 2, 1 Artur Alves Pessoa 3, 1 Eduardo Uchoa 1, 3 Issam Tahiri 2, 1 
1 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : Math heuristics have become an essential component in mixed integer programming (MIP) solvers. As the Dantzig-Wolfe reformulation of a problem is typically tighter than that of the original compact formulation, heuristics based on rounding its linear program- ing (LP) solution can be more competitive. We focus on the so-called diving methods that used re-optimization after each LP rounding. Our numerical results on generalized assignment, cutting stock, and vertex coloring problems sets new benchmarks, highlighting the performance of diving heuristics as generic procedures in a column generation context and producing better solutions than state-of-the-art specialized heuristics in some cases.
Document type :
Conference papers
Complete list of metadata
Contributor : François Vanderbeck Connect in order to contact the contributor
Submitted on : Tuesday, January 3, 2017 - 7:09:02 PM
Last modification on : Saturday, June 25, 2022 - 7:44:16 PM
Long-term archiving on: : Tuesday, April 4, 2017 - 3:16:41 PM


Files produced by the author(s)


  • HAL Id : hal-01425763, version 1



Ruslan Sadykov, François Vanderbeck, Artur Alves Pessoa, Eduardo Uchoa, Issam Tahiri. Recent results for column generation based diving heuristics. ColGen, May 2016, Buzios, Brazil. ⟨hal-01425763⟩



Record views


Files downloads