Universität zu Köln

Buchheim, Christoph ORCID: 0000-0001-9974-404X, Michaels, Dennis and Weismantel, Robert (2010). Integer Programming Subject to Monomial Constraints. SIAM journal on optimization : a publication of the Society for Industrial and Applied Mathematics, 20 (6). pp. 3297-3311. SIAM.

Preview

PDF zaik2009-591.pdf - Submitted Version Download (182kB) | Preview

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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Buchheim, Christoph UNSPECIFIED orcid.org/0000-0001-9974-404X UNSPECIFIED Michaels, Dennis UNSPECIFIED UNSPECIFIED UNSPECIFIED Weismantel, Robert UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-549880
Journal or Publication Title:	SIAM journal on optimization : a publication of the Society for Industrial and Applied Mathematics
Volume:	20
Number:	6
Page Range:	pp. 3297-3311
Date:	2010
Publisher:	SIAM
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54988