Primal Heuristics for Branch and Price: The Assets of Diving Methods

Ruslan Sadykov (), François Vanderbeck (), Artur Pessoa (), Issam Tahiri () and Eduardo Uchoa ()
Additional contact information
Ruslan Sadykov: Institute of Mathematics, University of Bordeaux, 33400 Talence, France, Inria Bordeaux Sud-Ouest Research Center, 33400 Talence, France
François Vanderbeck: Institute of Mathematics, University of Bordeaux, 33400 Talence, France, Inria Bordeaux Sud-Ouest Research Center, 33400 Talence, France
Artur Pessoa: Nú ucleo de Logistica Integrada e Sistemas LOGIS, Universidade Federal Fluminense, Niteró oi 24220-900, Brazil
Issam Tahiri: Institute of Mathematics, University of Bordeaux, 33400 Talence, France, Inria Bordeaux Sud-Ouest Research Center, 33400 Talence, France
Eduardo Uchoa: Nú ucleo de Logistica Integrada e Sistemas LOGIS, Universidade Federal Fluminense, Niteró oi 24220-900, Brazil

INFORMS Journal on Computing, 2019, vol. 31, issue 2, 251-267

Abstract: Primal heuristics have become essential components 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. Our heuristic decisions carry on variables of the Dantzig–Wolfe reformulation, the motivation being to take advantage of a tighter linear programming relaxation than that of the original compact formulation and to benefit from the combinatorial structure embedded in these variables. We focus on the so-called diving methods that use reoptimization after each linear programming rounding. We explore combinations with diversification-intensification paradigms such as limited discrepancy search , sub-MIP , 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 set 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.

Keywords: matheuristics; primal heuristics; rounding heuristics; diving heuristics; branch and price; column generation; generalized assignment; cutting stock; vertex coloring (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (26)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0822 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:2:p:251-267

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().