number theory

The Prime Programming Problem: Formulations and Solution Methods

  • Montree
  • Bismark Singh
    • Categories Integer Programming Tags , , , ,

    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 … Read more

    New Turnpike Theorems for the Unbounded Knapsack Problem

  • Ping H. Huang
  • Thomas L. Morin
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    We develop sharp bounds on turnpike theorems for the unbounded knapsack problem. Turnpike theorems specify when it is optimal to load at least one unit of the best item (i.e., the one with the highest “bang-for-buck” ratio) and, thus can be used for problem preprocessing. The successive application of the turnpike theorems can drastically reduce … Read more