Afficher la notice abrégée

Comparison of Bundle and Classical Column Generation

hal.structure.identifierOptimisation Combinatoire [G-SCOP_OC]
dc.contributor.authorBRIANT, Olivier
hal.structure.identifierModelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems [BIPOP]
dc.contributor.authorLEMARÉCHAL, Claude
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorMEURDESOIF, Philippe
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierLaboratoire de Mathématiques Appliquées du Havre [LMAH]
dc.contributor.authorMICHEL, Sophie
dc.contributor.authorPERROT, Nancy
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorVANDERBECK, François
dc.date.accessioned2024-04-04T02:44:14Z
dc.date.available2024-04-04T02:44:14Z
dc.date.issued2008-06
dc.identifier.issn0025-5610
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191392
dc.description.abstractEnWhen a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle method; our aim is to illustrate its differences with Kelley's method. In the process we review alternative stabilization techniques used in column generation, comparing them from both primal and dual points of view. Numerical comparisons are presented for five applications: cutting stock (which includes bin packing), vertex coloring, capacitated vehicle routing, multi-item lot sizing, and traveling salesman. We also give a sketchy comparison with the volume algorithm.
dc.language.isoen
dc.publisherSpringer Verlag
dc.subject.enNonsmooth convex optimization
dc.subject.enVolume algorithm
dc.subject.enBundle algorithm
dc.subject.enCutting-plane algorithms
dc.subject.enStabilized column generation
dc.subject.enDantzig-Wolfe decomposition
dc.subject.enLagrangian duality
dc.title.enComparison of Bundle and Classical Column Generation
dc.typeArticle de revue
dc.identifier.doi10.1007/s10107-006-0079-z
dc.subject.halMathématiques [math]/Optimisation et contrôle [math.OC]
bordeaux.journalMathematical Programming
bordeaux.page299-344
bordeaux.volume113
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue2
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierinria-00342510
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00342510v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Mathematical%20Programming&rft.date=2008-06&rft.volume=113&rft.issue=2&rft.spage=299-344&rft.epage=299-344&rft.eissn=0025-5610&rft.issn=0025-5610&rft.au=BRIANT,%20Olivier&LEMAR%C3%89CHAL,%20Claude&MEURDESOIF,%20Philippe&MICHEL,%20Sophie&PERROT,%20Nancy&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée