Skip to content CVSP — Paper guide | Fabio Furini Skip to content

PAPER GUIDE · MATHEMATICAL PROGRAMMING · 2015

Can Dantzig–Wolfe decomposition be automated?

Finding good decompositions of general mixed-integer programs without prior application-specific modelling knowledge.

M. Bergner · A. Caprara · A. Ceselli · F. Furini · M. E. Lübbecke · E. Malaguti · E. Traversi

General MIP matrixReordered blocksDantzig–Wolfereformulationcolumn generation
Conceptual illustration of the paper's methodology; drawn for this page, not reproduced from the published article.
THE CENTRAL INSIGHT

The idea is to discover a useful block structure automatically—even when the original constraint matrix does not visibly have one—and then exploit it through column generation.

01 / RESEARCH QUESTION

What makes this problem challenging?

Dantzig–Wolfe reformulation often gives strong dual bounds when a MIP has a bordered block-diagonal structure. Historically, identifying that structure and deciding how to decompose the model required an expert's knowledge of the application.

02 / THE IDEA

From problem structure to an algorithm

01Reveal candidate structures

Rearrange the constraint matrix using hypergraph partitioning, including bordered and double-bordered block-diagonal forms.

02Score decomposition quality

Use the relative border area as a computationally motivated proxy for the quality of candidate decompositions.

03Reformulate and solve

Apply Dantzig–Wolfe / related decomposition and column generation to promising candidates.

03 / ORIGINAL CONTRIBUTIONS

What does this work add?

Automatic structural detection

The paper demonstrates that many generic MIPs can be rearranged to admit a useful decomposition.

Relative border area

An experimentally motivated proxy measure to judge a decomposition before running the whole algorithm.

Beyond classical blocks

Double-bordered / arrowhead forms can be exploited via a variant of Lagrangian decomposition.

Computational proof of concept

Experiments on MIPLIB2003 and MIPLIB2010 show strong root-node dual bounds, sometimes with better overall computational performance, alongside marked variability.

04 / REPORTED FINDINGS

What does the study demonstrate?

On the studied medium-sized MIPLIB2003 and MIPLIB2010 instances, the automatic reformulations yielded, on average, root-node dual bounds comparable to or stronger than a state-of-the-art general MIP solver with standard settings. A non-negligible subset also showed improved overall performance, although results varied substantially across decompositions.

Grounded in Section 1.1 ('Our contribution') and the computational discussion in the published Mathematical Programming article. No unsupported numerical comparison has been added.

05 / READ MORE

The details are worth exploring.

For precise formulations, theorem statements, original figures and numerical tables, consult the published article.

Selected citing literature reviewed on 9 October 2026; examples are not ranked by citation counts.

06 / SUBSEQUENT RESEARCH

How other researchers have used this work

A selection of citing studies whose use of this contribution can be identified from the published paper.

A Data Driven Dantzig–Wolfe Decomposition Framework — Basso & Ceselli (2023) ↗

This study takes up the challenge of automatic MIP decomposition addressed in our paper and moves to a data-driven approach: learning to identify promising decompositions from algebraic features and evaluating them within a Dantzig–Wolfe framework. It cites our automatic-reformulation work as part of the methodological foundation.

Selective examples, not a comprehensive citation list. Descriptions refer to the cited studies' stated methodology and experiments.

Related methodological literature

Distributed asynchronous column generation (2022) ↗

The paper cites Bergner et al.'s automatic Dantzig–Wolfe reformulation as part of the column-generation and decomposition literature. Its contribution is distributed asynchronous column generation; a direct extension of the relative-border-area score has not been established here.

Mathematical Programming Computation (2023)

Integer programming column generation: accelerating branch-and-price using a novel pricing scheme ↗

Integrates a new pricing-based primal heuristic into GCG, a general branch-price-and-cut system that automatically detects Dantzig–Wolfe decomposition structures.

Computational Optimization and Applications (2023)

Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes ↗

Cites the original automatic Dantzig–Wolfe paper while studying the computational use of column generation for nonlinear and conic models. Related methodological context rather than direct reuse of the automatic decomposition score.

Annals of Operations Research (2020)

Random Sampling and Machine Learning to Understand Good Decompositions ↗

Moves the automatic decomposition question toward supervised and unsupervised learning, sampling MIP decomposition patterns and predicting which have promising computational properties; follows the research direction opened by automated Dantzig–Wolfe reformulation.