Martin Bergner

Automatic Dantzig-Wolfe Reformulation of Mixed Integer Programs

  • Martin Bergner
  • Alberto Caprara
  • Alberto Ceselli
  • Fabio Furini
  • Marco E. Lübbecke
  • Enrico Malaguti
  • Emiliano Traversi
    • Categories (Mixed) Integer Linear Programming Tags , , , , ,

    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 … Read more

    Partial Convexification of General MIPs by Dantzig-Wolfe Reformulation

  • Martin Bergner
  • Alberto Caprara
  • Fabio Furini
  • Marco E. Lübbecke
  • Enrico Malaguti
  • Emiliano Traversi
    • Categories (Mixed) Integer Linear Programming

    Dantzig-Wolfe decomposition is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs) in practice. However, the method is not part of any state-of-the-art MIP solver: it needs tailoring to the particular problem; the typical bordered block-diagonal matrix structure determines the decomposition; the resulting column generation subproblems need to be solved efficiently; … Read more