Optimizing Low Dimensional Functions over the Integers
share
We consider box-constrained integer programs with objective g(Wx) + c^T x, where g is a "complicated" function with an m dimensional domain. Here we assume we have n ≫ m variables and that W ∈ℤ^m × n is an integer matrix with coefficients of absolute value at most Δ. We design an algorithm for this problem using only the mild assumption that the objective can be optimized efficiently when all but m variables are fixed, yielding a running time of n^m(m Δ)^O(m^2). Moreover, we can avoid the term n^m in several special cases, in particular when c = 0. Our approach can be applied in a variety of settings, generalizing several recent results. An important application are convex objectives of low domain dimension, where we imply a recent result by Hunkenschröder et al. [SIOPT'22] for the 0-1-hypercube and sharp or separable convex g, assuming W is given explicitly. By avoiding the direct use of proximity results, which only holds when g is separable or sharp, we match their running time and generalize it for arbitrary convex functions. In the case where the objective is only accessible by an oracle and W is unknown, we further show that their proximity framework can be implemented in n (m Δ)^O(m^2)-time instead of n (m Δ)^O(m^3). Lastly, we extend the result by Eisenbrand and Weismantel [SODA'17, TALG'20] for integer programs with few constraints to a mixed-integer linear program setting where integer variables appear in only a small number of different constraints.
READ FULL TEXT