Integer Programming Subject to Monomial Constraints
Buchheim, Christoph and Michaels, Dennis and Weismantel, Robert
(2010)
Integer Programming Subject to Monomial Constraints.
Published in:
SIAM journal on optimization : a publication of the Society for Industrial and Applied Mathematics Vol. 20 (6).
pp. 3297-3311.
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.
Download: |
Download (182kB) | Preview |
---|---|
Editorial actions: | ![]() |
Item Type: | Article |
---|---|
Citations: | 0 (Google Scholar) | 0 (Web of Science) |
Uncontrolled Keywords: | monomial constraints nonlinear integer programming |
Subjects: |
|
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger |
Related URLs: |
ZAIK Number: | zaik2009-591 |
---|---|
Depositing User: | Christoph Buchheim |
Date Deposited: | 09 Jul 2009 00:00 |
Last Modified: | 09 Jan 2012 12:18 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/591 |