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. 32973311.
Abstract
We investigate integer programs containing monomial constraints. Due to the numbertheoretic 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: 
PDF
 Preprinted Version
Download (182kB)  Preview 

Export as:  [error in script] 
Editorial actions:  View Item (Login required) 
Item Type:  Article 

Citations:  [error in script] 0 (Google Scholar)  [error in script] 
Uncontrolled Keywords:  [error in script] 
Subjects: 

Uncontrolled Keywords:  monomial constraints, nonlinear integer programming 
Subjects:  90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C10 Integer programming 90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C30 Nonlinear programming 
Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Depositing User:  Christoph Buchheim 
Date Deposited:  09 Jul 2009 00:00 
Last Modified:  09 Jan 2012 12:18 
ZAIK Number:  [error in script] 

Depositing User:  Christoph Buchheim 
Date Deposited:  09 Jul 2009 00:00 
Last Modified:  09 Jan 2012 12:18 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/591 