Afficher la notice abrégée

hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorSADYKOV, Ruslan
hal.structure.identifierUniversidade Federal Fluminense [Rio de Janeiro] [UFF]
dc.contributor.authorPESSOA, Artur Alves
hal.structure.identifierUniversidade Federal Fluminense [Rio de Janeiro] [UFF]
dc.contributor.authorUCHOA, Eduardo
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-04T03:19:23Z
dc.date.available2024-04-04T03:19:23Z
dc.date.created2014-03
dc.date.conference2014-03-05
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/194505
dc.description.abstractEnColumn generation is a well-known method to solve large-scale combinatorial optimisation problem. However, its application in practice if often limited by convergence issues. To overcome this drawback, several stabilization techniques have been proposed. Probably, the most common techniques are 1) adding piecewise linear penalty functions to the dual objective and 2) dual price smoothing, which consists in pricing with a linear combination of the current dual solution and the best dual solution obtained earlier. Recently we proposed an automatic (parameter-less) variant of the dual price smoothing technique. In this work, we experimentally compare efficiency of the two mentioned stabilisation techniques on a wide range of problems, including machine scheduling, generalised assignment, lot sizing, capacitated vehicle routing, shift scheduling, and min-cost multi-commodity flow. Then, we also test numerically the combination of these techniques. Our experimental results show that for most problems this combination outperforms the two techniques applied separately.
dc.language.isoen
dc.title.enCombining dual price smoothing and piecewise linear penalty function stabilization in column generation: experimental results
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.title3rd International Symposium on Combinatorial Optimization ISCO'2014
bordeaux.countryPT
bordeaux.conference.cityLisbon
bordeaux.peerReviewedoui
hal.identifierhal-01104948
hal.version1
hal.invitednon
hal.proceedingsnon
hal.conference.end2014-03-07
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-01104948v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=SADYKOV,%20Ruslan&PESSOA,%20Artur%20Alves&UCHOA,%20Eduardo&VANDERBECK,%20Fran%C3%A7ois&rft.genre=unknown


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