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
Rearrange the constraint matrix using hypergraph partitioning, including bordered and double-bordered block-diagonal forms.
Use the relative border area as a computationally motivated proxy for the quality of candidate decompositions.
Apply Dantzig–Wolfe / related decomposition and column generation to promising candidates.
03 / ORIGINAL CONTRIBUTIONS
What does this work add?
The paper demonstrates that many generic MIPs can be rearranged to admit a useful decomposition.
An experimentally motivated proxy measure to judge a decomposition before running the whole algorithm.
Double-bordered / arrowhead forms can be exploited via a variant of Lagrangian decomposition.
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.