We introduce the prime programming problem as a subclass of integer programming. These optimization models impose the restriction of feasible solutions being prime numbers. Then, we demonstrate how several classical problems in number theory can be formulated as prime programs. To solve such problems with a commercial optimization solver, we extend the branch-and-bound procedure of integer programming. Next, in an effort to reduce the computational effort required by this branch-and-bound method, we utilize the special structure of prime numbers to incorporate new branching rules and variable fixing strategies. We present numerical results using a variety of such strategies on a classic conjecture on linear equations in prime numbers. Finally, by employing the concept of the inference dual of an integer program, we show how to perform sensitivity analysis on general prime programs; this allows us to to quickly compute changes in the optimal objective function value for small perturbations in the constraints. We publicly release all of our code to solve a general prime programming model.
Article
View The Prime Programming Problem: Formulations and Solution Methods