• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Automatic Dantzig–Wolfe reformulation of mixed integer programs

Bergner, Martin; Caprara, Alberto; Ceselli, Alberto; Furini, Fabio; Lübbecke, Marco E.; Malaguti, Enrico; Traversi, Emiliano (2015), Automatic Dantzig–Wolfe reformulation of mixed integer programs, Mathematical Programming, 149, 1-2, p. 391-424. 10.1007/s10107-014-0761-5

View/Open
3614.pdf (6.470Mb)
Type
Article accepté pour publication ou publié
Date
2015
Journal name
Mathematical Programming
Volume
149
Number
1-2
Publisher
Springer
Pages
391-424
Publication identifier
10.1007/s10107-014-0761-5
Metadata
Show full item record
Author(s)
Bergner, Martin

Caprara, Alberto
D.E.I. - University of Bologna.
Ceselli, Alberto
Università degli Studi di Milano
Furini, Fabio
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lübbecke, Marco E.

Malaguti, Enrico
D.E.I. - University of Bologna.
Traversi, Emiliano
Laboratoire d'Informatique de Paris-Nord [LIPN]
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.
Subjects / Keywords
Dantzig–Wolfe decomposition; Column generation; Block-diagonal matrix; Matrix re-ordering; Automatic reformulation; Hypergraph partitioning

Related items

Showing items related by title and author.

  • Thumbnail
    Solving the Temporal Knapsack Problem via Recursive Dantzig–Wolfe Reformulation 
    Caprara, Alberto; Furini, Fabio; Malaguti, Enrico; Traversi, Emiliano (2016) Article accepté pour publication ou publié
  • Thumbnail
    A hybrid heuristic for the multi-activity tour scheduling problem 
    Létocart, Lucas; Furini, Fabio; Liberti, Leo; Traversi, Emiliano; Bettiol, Enrico; Rinaldi, Francesco (2018) Article accepté pour publication ou publié
  • Thumbnail
    An exact algorithm for the Partition Coloring Problem 
    Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2018) Article accepté pour publication ou publié
  • Thumbnail
    An exact algorithm for the Partition Coloring Problem 
    Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2018) Article accepté pour publication ou publié
  • Thumbnail
    A note on selective line-graphs and partition colorings 
    Cornaz, Denis; Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2019) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo