"Integer Programming Subject to Monomial Constraints"
Technical report by Christoph Buchheim, Dennis Michaels, Robert Weismantel, available as BibTeX Source and in portable document format.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2009-591
Keywords:	monomial constraints, nonlinear integer programming
MSC codes:	90C10, 90C30
This technical report has 15 pages, was written in June 2009, it has not been published.
Abstract:	We investigate integer programs containing monomial constraints. Due to the number-theoretic nature of these constraints, standard methods based on linear algebra cannot be applied directly. Instead, we present a reformulation resulting in integer programs with linear constraints and polynomial objective functions, using prime decompositions of the right hand sides. Moreover, we show that minimizing a linear objective function with nonnegative coefficients over bivariate constraints is possible in polynomial time.