Decomposition of Sparse Integer Programs via Nonlinear Edge Encodings and Column-and-Row Generation
Abstract
A wide range of sparse integer programs admit a block structure in which subproblems interact through a small set of shared variables. Dualizing the linking equalities yields a decomposable Lagrangian relaxation, but generally introduces a duality gap. Recent work shows that this gap can be closed while preserving decomposability by dualizing exponentially large families of redundant nonlinear consistency constraints on the shared variables. We develop a computational framework for exploiting this idea without explicitly constructing the resulting exponentially large relaxation. Our framework combines nonlinear edge encodings of shared-variable consistency with a column-and-row generation (CRG) algorithm that generates local integer solutions by pricing and encoding constraints by separation. With complete encodings and exact separation, the framework recovers the exact relaxation while retaining independent optimization over the blocks. We introduce several encoding families and establish exponential separations among them: the Generalized family can require exponentially fewer constraints than the Vertex, Monomial, or Reflected families, yet can itself require exponentially many constraints on instances for which a single problem-specific encoding suffices. Computational experiments on decomposed stable-set and dominating-set instances show that CRG substantially outperforms a monolithic formulation across a range of tree topologies and coupling strengths. The results also show that richer encoding families need not perform better computationally, highlighting the choice of encoding as a central issue in effective decomposition.
Related
- Aggregated Column Generation for Two-Stage Stochastic Mixed-Integer Programs
- Integer decomposition property of three-dimensional smooth polytopes: a shorter proof
- Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging
- Satisfiability and freezing in random integer programs
- Accelerated Benders decomposition for bi-objective mixed integer programming
BibTeX
@misc{angulo2026decomposition,
title = {{Decomposition of Sparse Integer Programs via Nonlinear Edge Encodings and Column-and-Row Generation}},
author = {Gustavo Angulo and Santanu S. Dey},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05665},
eprint = {2609.05665},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05665},
}
RIS
TY - UNPB
TI - Decomposition of Sparse Integer Programs via Nonlinear Edge Encodings and Column-and-Row Generation
AU - Gustavo Angulo
AU - Santanu S. Dey
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05665
UR - https://arxiv.org/abs/2609.05665
AB - A wide range of sparse integer programs admit a block structure in which subproblems interact through a small set of shared variables. Dualizing the linking equalities yields a decomposable Lagrangian relaxation, but generally introduces a duality gap. Recent work shows that this gap can be closed while preserving decomposability by dualizing exponentially large families of redundant nonlinear consistency constraints on the shared variables. We develop a computational framework for exploiting this idea without explicitly constructing the resulting exponentially large relaxation. Our framework combines nonlinear edge encodings of shared-variable consistency with a column-and-row generation (CRG) algorithm that generates local integer solutions by pricing and encoding constraints by separation. With complete encodings and exact separation, the framework recovers the exact relaxation while retaining independent optimization over the blocks. We introduce several encoding families and establish exponential separations among them: the Generalized family can require exponentially fewer constraints than the Vertex, Monomial, or Reflected families, yet can itself require exponentially many constraints on instances for which a single problem-specific encoding suffices. Computational experiments on decomposed stable-set and dominating-set instances show that CRG substantially outperforms a monolithic formulation across a range of tree topologies and coupling strengths. The results also show that richer encoding families need not perform better computationally, highlighting the choice of encoding as a central issue in effective decomposition.
ER -