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.


Actions:
Download: [img] PDF - Preprinted Version
Download (178Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 0 (Google Scholar) | 0 (Web of Science)
Uncontrolled Keywords: monomial constraints nonlinear integer programming
Subjects:
  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C10 Integer programming

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C30 Nonlinear programming

    		•
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Related URLs:
    Deposit Information:
    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