Recent results for column generation based diving heuristics

Ruslan Sadykov 1, 2 François Vanderbeck 2, 1 Artur 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 metadatas

https://hal.inria.fr/hal-01425763
Contributor : François Vanderbeck <>
Submitted on : Tuesday, January 3, 2017 - 7:09:02 PM
Last modification on : Friday, December 14, 2018 - 11:34:01 AM
Long-term archiving on : Tuesday, April 4, 2017 - 3:16:41 PM

File

Sadykov.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01425763, version 1

Citation

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

Share

Metrics

Record views

514

Files downloads

77