Primal Heuristics for Branch-and-Price: the assets of diving methods
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | SADYKOV, Ruslan | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | VANDERBECK, François | |
| hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
| dc.contributor.author | PESSOA, Artur | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | TAHIRI, Issam | |
| hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
| dc.contributor.author | UCHOA, Eduardo | |
| dc.date.accessioned | 2024-04-04T03:10:19Z | |
| dc.date.available | 2024-04-04T03:10:19Z | |
| dc.date.issued | 2019 | |
| dc.identifier.issn | 1091-9856 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193679 | |
| dc.description.abstractEn | Primal 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. 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 re-optimization after each LP rounding. We explore combinations with diversification- intensification paradigms such as limited discrepancy search , sub-MIPing, 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. | |
| dc.language.iso | en | |
| dc.publisher | Institute for Operations Research and the Management Sciences (INFORMS) | |
| dc.subject.en | Vertex Coloring | |
| dc.subject.en | Cutting Stock | |
| dc.subject.en | Mathheuristics | |
| dc.subject.en | Diving Heuristics | |
| dc.subject.en | Generalized Assignment | |
| dc.subject.en | Column Generation | |
| dc.subject.en | Primal Heuristics | |
| dc.subject.en | Branch-and-Price | |
| dc.subject.en | Rounding Heuristics | |
| dc.title.en | Primal Heuristics for Branch-and-Price: the assets of diving methods | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1287/ijoc.2018.0822 | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | INFORMS Journal on Computing | |
| bordeaux.page | 251-267 | |
| bordeaux.volume | 31 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 2 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01237204 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01237204v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=INFORMS%20Journal%20on%20Computing&rft.date=2019&rft.volume=31&rft.issue=2&rft.spage=251-267&rft.epage=251-267&rft.eissn=1091-9856&rft.issn=1091-9856&rft.au=SADYKOV,%20Ruslan&VANDERBECK,%20Fran%C3%A7ois&PESSOA,%20Artur&TAHIRI,%20Issam&UCHOA,%20Eduardo&rft.genre=article |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||