Afficher la notice abrégée

Column Generation for Extended Formulations

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.authorVANDERBECK, François
dc.date.accessioned2024-04-04T02:22:34Z
dc.date.available2024-04-04T02:22:34Z
dc.date.issued2013-05-01
dc.identifier.issn2192-4406
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/189661
dc.description.abstractEnWorking in an extended variable space allows one to develop tighter reformu- lations for mixed integer programs. However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. Then, one can work with inner approximations defined and improved by generating dynamically vari- ables and constraints. When the extended formulation stems from subproblems' reformulations, one can implement column generation for the extended formulation using a Dantzig-Wolfe decomposition paradigm. Pricing subproblem solutions are expressed in the variables of the extended formulation and added to the current re- stricted version of the extended formulation along with the subproblem constraints that are active for the subproblem solutions. This so-called "column-and-row gen- eration" procedure is revisited here in a unifying presentation that generalizes the column generation algorithm and extends to the case of working with an approximate extended formulation. The interest of the approach is evaluated numerically on ma- chine scheduling, bin packing, generalized assignment, and multi-echelon lot-sizing problems. We compare a direct handling of the extended formulation, a standard column generation approach, and the "column-and-row generation" procedure, high- lighting a key benefit of the latter: lifting pricing problem solutions in the space of the extended formulation permits their recombination into new subproblem solutions and results in faster convergence.
dc.language.isoen
dc.publisherSpringer
dc.title.enColumn Generation for Extended Formulations
dc.typeArticle de revue
dc.identifier.doi10.1007/s13675-013-0009-9
dc.subject.halMathématiques [math]/Optimisation et contrôle [math.OC]
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalEURO Journal on Computational Optimization
bordeaux.page81-115
bordeaux.volume1
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue1-2
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00661758
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00661758v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=EURO%20Journal%20on%20Computational%20Optimization&rft.date=2013-05-01&rft.volume=1&rft.issue=1-2&rft.spage=81-115&rft.epage=81-115&rft.eissn=2192-4406&rft.issn=2192-4406&rft.au=SADYKOV,%20Ruslan&VANDERBECK,%20Fran%C3%A7ois&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