Value Functions of Separable Convex Integer Programs are Periodically Convex
Abstract
We consider the periodic behavior of value functions b↦min{f(x) | Ax=b, x∈ℤ≥0n} of integer programs. We show that there exists a positive integer M depending only on the constraint matrix A∈ℤm× n so that the value function is convex extensible on any subdomain of the form r+Mℤm for any r∈ℤm and any separable convex objective function f. With this, we extend the known periodic convexity of such functions for linear objective functions f, as established by Eisenbrand and Rothvoss (SODA 26), to the broader class of separable convex objective functions. We derive our main periodic convexity result by first showing that periodic convexity along lines is equivalent to the integer decomposition property of dilated polyhedra. Subsequently, we use Graver basis techniques to extend the $1$-dimensional periodic convexity to domains of arbitrary fixed dimension. We apply this periodic convexity to show that value function reformulations of block-structured integer programs become periodically convex, which yields fixed-parameter tractable (FPT) algorithms. More specifically, we optimize two-stage stochastic integer programs and n-fold integer programs in FPT time when parameterized by the block dimensions and coefficient size of the local blocks of the constraint matrix, allowing the coefficients of the global blocks to be large. In the setting of this parameterization, which was recently introduced by Cslovjecsek, Koutecký, Lassota, Pilipczuk, and Polak (TheoretiCS 2025), our algorithms exponentially improve on the running times of the previous optimization algorithms and extend the class of objective functions that can be optimized from linear to separable convex.
Related
- A Characterization of Functions on the Integer Lattice That Are L-Extendable through Local Convex Extensions
- Zeros of Melnikov functions for periodically perturbed Hamiltonian systems with random coefficients
- Smooth or Separable? Sparse Block Acceleration for Entropy-Regularized Linear Programs
- Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging
- Satisfiability and freezing in random integer programs
BibTeX
@misc{ligthart2026value,
title = {{Value Functions of Separable Convex Integer Programs are Periodically Convex}},
author = {Koen Ligthart},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.30330},
eprint = {2606.30330},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.30330},
}
RIS
TY - UNPB
TI - Value Functions of Separable Convex Integer Programs are Periodically Convex
AU - Koen Ligthart
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2606.30330
UR - https://arxiv.org/abs/2606.30330
AB - We consider the periodic behavior of value functions b↦min{f(x) | Ax=b, x∈ℤ_≥0^n} of integer programs. We show that there exists a positive integer M depending only on the constraint matrix A∈ℤ^m× n so that the value function is convex extensible on any subdomain of the form r+Mℤ^m for any r∈ℤ^m and any separable convex objective function f. With this, we extend the known periodic convexity of such functions for linear objective functions f, as established by Eisenbrand and Rothvoss (SODA 26), to the broader class of separable convex objective functions. We derive our main periodic convexity result by first showing that periodic convexity along lines is equivalent to the integer decomposition property of dilated polyhedra. Subsequently, we use Graver basis techniques to extend the $1$-dimensional periodic convexity to domains of arbitrary fixed dimension. We apply this periodic convexity to show that value function reformulations of block-structured integer programs become periodically convex, which yields fixed-parameter tractable (FPT) algorithms. More specifically, we optimize two-stage stochastic integer programs and n-fold integer programs in FPT time when parameterized by the block dimensions and coefficient size of the local blocks of the constraint matrix, allowing the coefficients of the global blocks to be large. In the setting of this parameterization, which was recently introduced by Cslovjecsek, Koutecký, Lassota, Pilipczuk, and Polak (TheoretiCS 2025), our algorithms exponentially improve on the running times of the previous optimization algorithms and extend the class of objective functions that can be optimized from linear to separable convex.
ER -