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:28:07Z
dc.date.available2024-04-04T02:28:07Z
dc.date.issued2011
dc.date.conference2011-03-28
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/190072
dc.description.abstractEnWorking in an extended variable space allows one to develop tight reformulations 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 use projection tools to derive valid inequalities for the original formulation and implement a cutting plane approach. Or, one can approximate the reformulation, using techniques such as variable aggregation or reformulation of a submodel only. These approaches result in working with an outer approximation of the intended extended formulation. The alternative considered here is an inner approximation obtained by generating dynamically the variables of the extended formulation. It assumes that the extended formulation stems from a decomposition principle: a subproblem admits an extended formulation from which an extended formulation for the global problem can be derived. Then, one can implement column generation for the extended formulation mimicking that procedure for the Dantzig-Wolfe reformulation. Pricing subproblem solutions are expressed in the variables of the extended formulation and added to the current restricted version of the extended formulation along with the subproblem constraints that are active for the subproblem solution. The paper reviews the applications of such ``column-and-row generation'' procedure from the literature and analyses this approach's potential benefits compared to a standard column generation approach. Numerical experiments highlight a key observation: 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.publisherElsvier
dc.title.enColumn Generation for Extended Formulations
dc.typeCommunication dans un congrès
dc.identifier.doi10.1016/j.endm.2011.05.061
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.page357-362
bordeaux.volume37
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.title6th Latin-American Algorithms, Graphs and Optimization Symposium
bordeaux.countryAR
bordeaux.conference.cityBariloche
bordeaux.peerReviewedoui
bordeaux.type.reportrr
hal.identifierinria-00539870
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2011-04-01
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00539870v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2011&rft.volume=37&rft.spage=357-362&rft.epage=357-362&rft.au=SADYKOV,%20Ruslan&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