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.
Type de document :
Communication dans un congrès
ColGen, May 2016, Buzios, Brazil. 2016
Liste complète des métadonnées

https://hal.inria.fr/hal-01425763
Contributeur : François Vanderbeck <>
Soumis le : mardi 3 janvier 2017 - 19:09:02
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : mardi 4 avril 2017 - 15:16:41

Fichier

Sadykov.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01425763, version 1

Collections

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. 2016. 〈hal-01425763〉

Partager

Métriques

Consultations de la notice

456

Téléchargements de fichiers

32