• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Automatic Dantzig–Wolfe reformulation of mixed integer programs

Thumbnail
View/Open
3614.pdf (6.470Mb)
Date
2015
Dewey
Recherche opérationnelle
Sujet
Dantzig–Wolfe decomposition; Column generation; Block-diagonal matrix; Matrix re-ordering; Automatic reformulation; Hypergraph partitioning
Journal issue
Mathematical Programming
Volume
149
Number
1-2
Publication date
2015
Article pages
391-424
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s10107-014-0761-5
URI
https://basepub.dauphine.fr/handle/123456789/12863
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bergner, Martin
status unknown
Caprara, Alberto
461036 D.E.I. - University of Bologna.
Ceselli, Alberto
413061 Università degli Studi di Milano
Furini, Fabio
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lübbecke, Marco E.
status unknown
Malaguti, Enrico
461036 D.E.I. - University of Bologna.
Traversi, Emiliano
994 Laboratoire d'Informatique de Paris-Nord [LIPN]
Type
Article accepté pour publication ou publié
Abstract (EN)
Dantzig–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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.