  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\leq b,\ \gamma^\top x\equiv r\pmod{m},\
x\in\mathbb{Z}^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\times 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.
