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.


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: [img] PDF - Preprinted Version
Download (182kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2009-591
Depositing User: Christoph Buchheim
Date Deposited: 09 Jul 2009 00:00
Last Modified: 09 Jan 2012 12:18