Optimization Modulo Integer Linear-Exponential Programs

This paper presents the first study of the complexity of the optimization problem for integer linear-exponential programs which extend classical integer linear programs with the exponential function \(x \mapsto 2^x\) and the remainder function \((x,y) \mapsto (x \bmod 2^y)\). The problem of deciding if such a program has a solution was recently shown to be NP-complete in [Chistikov et al., ICALP’24]. The optimization problem instead asks for a solution that maximizes (or minimizes) a linear-exponential objective function, subject to the constraints of an integer linear-exponential program.