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. Our approach makes use of the Graver basis, an optimality certificate for integer programs, which we characterize as corresponding to the collection of induced connected subgraphs of our graph. 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 improving moves from the Graver basis 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.