Congruency-Constrained TU Problems Beyond the Bimodular Case
成果类型：
Article
署名作者：
Naegele, Martin; Santiago, Richard; Zenklusen, Rico
署名单位：
University of Bonn
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2023.1381
发表日期：
2024
关键词：
摘要：
A long-standing open question in integer programming is whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable. An important special case thereof are congruency-constrained integer programs min{c(inverted perpendicular)x : Tx <= b, gamma(inverted perpendicular)x = r (mod m), x is an element of Z(n)} with a totally unimodular constraint matrix T. Such problems are shown to be polynomial-time solvable for m = 2, which led to an efficient algorithm for integer programs with bimodular constraint matrices, that is, full-rank matrices whose n x n subdeterminants are bounded by two in absolute value. Whereas these advances heavily rely on existing results on well-known combinatorial problems with parity constraints, new approaches are needed beyond the bimodular case, that is, for m > 2. We make first progress in this direction through several new techniques. In particular, we show how to efficiently decide feasibility of congruency-constrained integer programs with a totally unimodular constraint matrix for m = 3 using a randomized algorithm. Furthermore, for general m, our techniques also allow for identifying flat directions of infeasible problems and deducing bounds on the proximity between solutions of the problem and its relaxation.
来源URL：