{"id":"arxiv/2609.05665","url":"https://arxiv.org/abs/2609.05665","tags":["math.OC"],"score":0,"title":"Decomposition of Sparse Integer Programs via Nonlinear Edge Encodings and Column-and-Row Generation","domain":"math.OC","source":"arxiv","authors":["Gustavo Angulo","Santanu S. Dey"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-04","reactions":{}}