Show simple item record

dc.contributor.authorBergner, Martin*
dc.contributor.authorCaprara, Alberto*
dc.contributor.authorCeselli, Alberto*
dc.contributor.authorFurini, Fabio*
dc.contributor.authorLübbecke, Marco E.*
dc.contributor.authorMalaguti, Enrico*
dc.contributor.authorTraversi, Emiliano*
dc.date.accessioned2014-03-11T17:43:07Z
dc.date.available2014-03-11T17:43:07Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/12863
dc.language.isoenen
dc.subjectDantzig–Wolfe decompositionen
dc.subjectColumn generationen
dc.subjectBlock-diagonal matrixen
dc.subjectMatrix re-orderingen
dc.subjectAutomatic reformulationen
dc.subjectHypergraph partitioningen
dc.subject.ddc003en
dc.titleAutomatic Dantzig–Wolfe reformulation of mixed integer programsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenDantzig–Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the method is not implemented in any state-of-the-art MIP solver as it is considered to require structural problem knowledge and tailoring to this structure. We provide a computational proof-of-concept that the reformulation can be automated. That is, we perform a rigorous experimental study, which results in identifying a score to estimate the quality of a decomposition: after building a set of potentially good candidates, we exploit such a score to detect which decomposition might be useful for Dantzig–Wolfe reformulation of a MIP. We experiment with general instances from MIPLIB2003 and MIPLIB2010 for which a decomposition method would not be the first choice, and demonstrate that strong dual bounds can be obtained from the automatically reformulated model using column generation. Our findings support the idea that Dantzig–Wolfe reformulation may hold more promise as a general-purpose tool than previously acknowledged by the research community.en
dc.relation.isversionofjnlnameMathematical Programming
dc.relation.isversionofjnlvol149
dc.relation.isversionofjnlissue1-2
dc.relation.isversionofjnldate2015
dc.relation.isversionofjnlpages391-424
dc.relation.isversionofdoi10.1007/s10107-014-0761-5en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.person.labIds245746*
hal.person.labIds461036*
hal.person.labIds413061*
hal.person.labIds989*
hal.person.labIds245746*
hal.person.labIds461036*
hal.person.labIds994*
hal.faultCode{"duplicate-entry":{"hal-01504852":{"doi":"1.0"}}}


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record