Augmentation algorithms for integer programs with total variation-like regularization

We address a class of integer optimization programs with a total variation-like regularizer and convex, separable constraints on a graph. To solve this problem, we employ an augmentation algorithm which operates by repeatedly updating our solution on variables corresponding to induced connected subgraphs of the graph. This set of moves is derived from the set of circuits of the underlying constraint matrix, and due to the total unimodularity of the constraint matrix, this set acts as an optimality certificate for the integer programs. We demonstrate how to use this basis to craft an exact global optimization algorithm for the unconstrained problem recovering a method first shown by Kolmogorov and Shioura in 2009. We then address the problem with an additional budget constraint with a randomized heuristic algorithm that samples connected subgraphs in a randomized variant of the simplex algorithm. Through comprehensive experiments, we demonstrate that this randomized algorithm is competitive with and often outperforms state-of-the-art integer program solvers.