Title




Integer programming with GCD constraints
 
Author




 
Abstract




We study the nonlinear extension of integer programming with greatest common divisor constraints of the form gcd(f, g) ~ d, where f and g are linear polynomials, d is a positive integer, and ~ is a relation among ≤, = ≠, = and ≥. We show that the feasibility problem for these systems is in NP, and that an optimal solution minimizing a linear objective function, if it exists, has polynomial bit length. To show these results, we identify an expressive fragment of the existential theory of the integers with addition and divisibility that admits solutions of polynomial bit length. It was shown by Lipshitz [Trans. Am. Math. Soc., 235, pp. 271283, 1978] that this theory adheres to a localtoglobal principle in the following sense: a formula Φ is equisatisfiable with a formula Ψ in this theory such that Ψ has a solution if and only if Ψ has a solution modulo every prime p. We show that in our fragment, only a polynomial number of primes of polynomial bit length need to be considered, and that the solutions modulo prime numbers can be combined to yield a solution to Φ of polynomial bit length. As a technical byproduct, we establish a Chineseremaindertype theorem for systems of congruences and noncongruences showing that solution sizes do not depend on the magnitude of the moduli of noncongruences. 
 
Language




English
 
Source (book)




Proceedings of the 2024 ACMSIAM Symposium on Discrete Algorithms (SODA)
 
Publication




2024
 
ISBN




9781611977912
 
DOI




10.1137/1.9781611977912.128
 
Volume/pages




p. 36053658
 
Full text (Publisher's DOI)




 
Full text (open access)




 
Full text (publisher's version  intranet only)




 
