Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Primal Heuristics for Branch-and-Price: the assets of diving methods

Ruslan Sadykov 1 François Vanderbeck 1, 2 Artur Pessoa 3 Issam Tahiri 1, 2 Eduardo Uchoa 3
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. Extending MIP based heuristics, our study outlines generic procedures to build primal solutions in the context of a branch-and-price approach and reports on their performance. As the Dantzig-Wolfe reformulation of a problem is typically tighter than that of the original compact formulation, heuristics based on rounding its linear programing (LP) solution can be more competitive. We focus on the so-called diving methods that used re-optimization after each LP rounding. We explore combination with diversification- intensification paradigms such as Limited Discrepancy Search, sub-MIPing, relaxation induced neighborhood search, local branching, and strong branching. The dynamic generation of variables inherent to a column generation approach requires specific adaptation of heuristic paradigms. We manage to use simple strategies to get around these technical issues. 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 :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/hal-01237204
Contributor : François Vanderbeck <>
Submitted on : Tuesday, January 3, 2017 - 5:13:28 PM
Last modification on : Tuesday, January 14, 2020 - 10:26:41 AM

File

wpv2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01237204, version 2

Citation

Ruslan Sadykov, François Vanderbeck, Artur Pessoa, Issam Tahiri, Eduardo Uchoa. Primal Heuristics for Branch-and-Price: the assets of diving methods. 2016. ⟨hal-01237204v2⟩

Share

Metrics

Record views

263

Files downloads

647