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 → 2 x and the remainder function (x, y) → (x mod 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. We establish the following results:

• If an optimal solution exists, then one of them can be succinctly represented as an integer linear-exponential straight-line program (ILESLP): an arithmetic circuit whose gates always output an integer value (by construction) and implement the operations of addition, exponentiation, and multiplication by rational numbers.