Show simple item record

Column Generation based Primal Heuristics

hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorJONCOUR, Cédric
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierLaboratoire de Mathématiques Appliquées du Havre [LMAH]
dc.contributor.authorMICHEL, Sophie
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorSADYKOV, Ruslan
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorSVERDLOV, Dmitry
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorVANDERBECK, François
dc.date.accessioned2024-04-04T02:22:34Z
dc.date.available2024-04-04T02:22:34Z
dc.date.issued2010-03-24
dc.date.conference2010-03-24
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/189662
dc.description.abstractEnIn the past decade, significant progress has been achieved in developing generic primal heuristics that made their way into commercial mixed integer programming (MIP) solver. Extensions to the context of a column generation solution approach are not straightforward. The Dantzig-Wolfe decomposition principle can indeed be exploited in greedy, local search, rounding or truncated exact methods. The price coordination mechanism can bring a global view that may be lacking in some ''myopic'' approaches based on a compact formulation. However, the dynamic generation of variables requires specific adaptation of heuristic paradigms. The column generation literature reports many application specific studies where primal heuristics are a key to success. There remains to extract generic methods that could be seen as black-box primal heuristics for use across applications. In this paper we review generic classes of column generation based primal heuristics. We then focus on a so-called ''diving'' method in which we introduce diversification based on Limited Discrepancy Search. While being a general purpose approach, the implementation of our heuristic illustrates the technicalities specific to column generation. The method is numerically tested on variants of the cutting stock and vehicle routing problems.
dc.language.isoen
dc.title.enColumn Generation based Primal Heuristics
dc.typeCommunication dans un congrès
dc.identifier.doi10.1016/j.endm.2010.05.088
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.page695-702
bordeaux.volume36
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleInternational Symposium on Combinatorial Optimization (ISCO)
bordeaux.countryTN
bordeaux.conference.cityHaMMamet
bordeaux.peerReviewedoui
hal.identifierhal-00790610
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2010-03-26
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00790610v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2010-03-24&rft.volume=36&rft.spage=695-702&rft.epage=695-702&rft.au=JONCOUR,%20C%C3%A9dric&MICHEL,%20Sophie&SADYKOV,%20Ruslan&SVERDLOV,%20Dmitry&VANDERBECK,%20Fran%C3%A7ois&rft.genre=unknown


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record