Augmentation Algorithms for Integer Programs with Total Variation-like Regularization
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911113215475712 |
|---|---|
| author | Yang, Dominic Leyffer, Sven Bakenhus, Miles |
| author_facet | Yang, Dominic Leyffer, Sven Bakenhus, Miles |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_05822 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Augmentation Algorithms for Integer Programs with Total Variation-like Regularization Yang, Dominic Leyffer, Sven Bakenhus, Miles Optimization and Control 90C27 (Primary), 90C59, 90C10 (Secondary) 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. |
| title | Augmentation Algorithms for Integer Programs with Total Variation-like Regularization |
| topic | Optimization and Control 90C27 (Primary), 90C59, 90C10 (Secondary) |
| url | https://arxiv.org/abs/2508.05822 |