2021/09/07 by Nägele, Martin, Santiago, Richard, Zenklusen, Rico · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2109.03148
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^\top x\colon Tx≤ b, γ^\top x≡ r\pmodm, x∈ℤn\ with a totally unimodular constraint matrix T. Such problems have been shown to be polynomial-time solvable for m=2, which led to an efficient algorithm for integer programs with bimodular constraint matrices, i.e., full-rank matrices whose n× n subdeterminants are bounded by two in absolute value. Whereas these advances heavily relied on existing results on well-known combinatorial problems with parity constraints, new approaches are needed beyond the bimodular case, i.e., 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. 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.