Augmentation Algorithms for Integer Programs with Total Variation-like Regularization
Dominic Yang, Sven Leyffer, Miles Bakenhus · 2025
Read Augmentation Algorithms for Integer Programs with Total Variation-like Regularization by Dominic Yang, Sven Leyffer, Miles Bakenhus (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-05822.txt.
Introduction
Yang, Leyffer, and Bakenhus craft algorithms for integer programs with a total-variation-like penalty on a graph. Constraints are convex and separable across the graph's parts. Their key tool is the Graver basis, an optimality certificate for integer programs.
They show that basis matches the graph's induced connected subgraphs. With it, they rebuild an exact global method first shown by Kolmogorov and Shioura in 2009. For a version with a budget limit, they add a randomized heuristic. It samples improving moves from the basis in a simplex-style search. Wide tests show the heuristic often beats top general integer solvers.
Catalog record
| CREATOR | Dominic Yang, Sven Leyffer, Miles Bakenhus |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 82 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-05822
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Augmentation Algorithms for Integer Programs with Total Variation-like Regularization Dominic Yang, Sven Leyffer, Miles Bakenhus Abstract 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. MSC Classification]90C27, 90C59, 90C10 keywords Randomized Algorithms, Graver Bases, Simplex Method, Combinatorial Optimization pacs [ 1 Introduction We address combinatorial optimization problems of the following form: \displaystyle\min_{x\in\mathbb{Z}^{n}}\qquad \displaystyle J(x):=\sum_{v\in\Vcal}F_{v}(x_{v})+\sum_{uv\in\Ecal}G_{uv}(x_{u}-x_{v}) (1a) s.t. \displaystyle\sum_{v\in\Vcal}H_{v}(x_{v})\leq\Delta, (1b) \displaystyle x\in\{0,\dots,Q\}^{\Vcal}, (1c) where we have an associated directed graph \Gcal=(\Vcal,\Ecal) ; F_{v}, G_{uv}, and H_{v} are univariate functions that are assumed to be convex; and Q\in\mathbb{Z}_{\geq 0} and \Delta\geq 0 are given parameters. We define F(x)=\sum_{v\in\Vcal}F_{v}(x),\quad G(x)=\sum_{uv\in\Ecal}G_{uv}(x_{u}-x_{v}),\quad\text{and}\quad H(x)=\sum_{v}H_{v}(x_{v}). (2) We refer to the constraint H as the budget constraint for ( 1 ). Despite its simple form, this is a challenging combinatorial optimization problem with a number of important applications, including image denoising Rudin et al. 1992 and topology optimization Manns and Severitt 2024 . In the absence of constraint ( 1b ), this problem was studied in the late 1990s and 2000s extensively in the computer vision and pattern recognition community, and most algorithms addressing this problem use a minimum cut approach. In 1998 Ishikawa and Geiger 1998 (and later refined in 2003 Ishikawa 2003 ), Ishikawa produced one of the first exact algorithms for solving the unconstrained problem even when F_{v} are general functions. We note in particular the method of Kolmogorov and Shioura in Kolmogorov and Shioura 2009 that exploits the fact that J is an L^{\natural} -convex function for which there are known polynomial-time algorithms (see Murota et al. 2004 ; Murota 2004 for definitions and algorithms). For this class of functions, it is known that if at a given point x , J(x)\leq J(x\pm\chi_{X}) for all choices of X\subset\Vcal where x\pm\chi_{X} is feasible, x is globally optimal. This leads to a simple augmentation routine shown in Algorithm 1 that repeatedly solves binary optimization problems to determine the subsets X to increment or decrement on, each of which can be found by solving an associated minimum cut problem. Data: x^{(0)}\in\{0,1,\ldots,Q\}^{\Vcal} k\leftarrow 0 while True do \Delta x^{\text{up}}\leftarrow\text{argmin}_{\Delta x\in\{0,1\}^{\Vcal},x^{(k)}+\Delta x\leq Q}J(x^{(k)}+\Delta x) x^{(k+1)}\leftarrow x^{(k)}+\Delta x^{\text{up}} \Delta x^{\text{down}}\leftarrow\text{argmin}_{\Delta x\in\{0,1\}^{\Vcal},x^{(k+1)}-\Delta x\geq 0}J(x^{(k+1)}-\Delta x) x^{(k+2)}\leftarrow x^{(k+1)}-\Delta x^{\text{down}} if x^{(k+2)}=x^{(k)} then // Neither Augmentation Changed x return x^{(k)} // Point is Optimal k\leftarrow k+2 Algorithm 1 Augmentation Algorithm for Unconstrained Version of ( 1 ) (from Kolmogorov and Shioura 2009 ) The methods we develop in this paper bear similarity to this approach, but we ground our reasoning in the context of Graver basis augmentation methods. The Graver basis, first introduced in Graver 1975 , is a collection of vectors associated with a given integer matrix A that most importantly serve as an optimality certificate for any integer program with a convex, separable objective that uses A as its constraint matrix (see De Loera et al. 2012 for a comprehensive introduction). In Theorem 1 we establish the structure of the Graver basis for matrix A_{TV} associated with the constraints \{x_{u}-x_{v}=a_{uv}\}_{uv\in\Ecal} establishing that \{\pm\chi_{S}:S\subset\Vcal,S\text{ induces a connected subgraph}\} is an optimality certificate for ( 1 ). Hence, instead of optimizing over all subsets of \{0,1\}^{\Vcal} , we can modify each of the subproblem solves in Algorithm 1 to consider only subsets that induce connected subgraphs. This alternate basis presents an opportunity for the development of randomized heuristics where we sample these connected subgraphs. In this sense we are now modifying Algorithm 1 to replace the exact subproblem solves with randomized approximate solves given by sampling the Graver basis. Since A_{TV} is well known to be totally unimodular, edges of any polytope where A_{TV} is the constraint matrix are necessarily integer multiples of Graver basis elements Thomas 1995 . Therefore, algorithms that traverse the edges of the underlying polytope, in particular primal simplex methods, effectively perform Graver basis augmentation algorithms. In our work we establish how to randomize the operation of a primal simplex method to sample improving Graver augmentations as well as adapt the method to ensure feasibility according to the constraint ( 1b ). Related Work. Several other polynomial-time algorithms exist for handling the unconstrained version of ( 1 ). In Ahuja et al. 2004 and Hochbaum 2001 , the authors present minimum cut algorithms for solving the problem. Boykov et al. in Boykov et al. 2002 and Boykov and Kolmogorov 2004 address the more general situation where G_{uv} is an arbitrary function of two variables and provide approximation guarantees for their algorithm. The authors in Bioucas-Dias and Valadao 2007 address specifically the case without the first term F . The full problem with the budgetary constraint included has seen comparatively less study in the literature. It is known to contain NP-hard problems including finding a minimum s-t cut of a directed graph with a bound on the number of vertices on one side (shown in Armon and Zwick 2006 ). Recently, a few papers by Manns and Severitt have focused on the case where F is linear, G is the total variation, and H restricts the feasible space to be in a 1-norm ball about a given point. In Severitt and Manns 2023 , they study a one-dimensional variant of the total variation, i.e., where the underlying graph in ( 1 ) is a path graph and they give a polynomial algorithm for this setting. In Manns and Severitt 2024 , they study the two-dimensional version of the anisotropic total variation where the underlying graph is an M\times N grid and give primal heuristics, branching rules and methods for producing cutting planes for this problem. We are broadly interested in problems where G_{uv} is the absolute value, in which case G is understood to be the total variation (TV) of x with respect to the underlying graph \Gcal first introduced as a regularizer in Rudin et al. 1992 . In its original context as an image denoiser, it was notable for its ability to smooth the solution while still preserving sharp curves in the image. A few papers Zalesky 2002 ; Chambolle 2005 also specifically address the unconstrained version of ( 1 ) where G is the anisotropic total variation of a graph. Recently, it has seen use in the context of topology optimization Manns and Severitt 2024 ; Severitt and Manns 2023 in order to limit speckle patterns in produced solutions. We now review two applications of ( 1 ) where the total variation is explicitly used as a regularizer which we will refer to later in the paper. Total Variation Denoising. The classic setting for problems of the form (