Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

A polyhedral Frobenius theorem with applications to integer optimization

Adjiashvili, David, Oertel, Timm and Weismantel, Robert 2015. A polyhedral Frobenius theorem with applications to integer optimization. SIAM Journal on Discrete Mathematics 29 (3) , pp. 1287-1302. 10.1137/14M0973694

[img]
Preview
PDF - Accepted Post-Print Version
Download (364kB) | Preview

Abstract

We prove a representation theorem of projections of sets of integer points by an integer matrix $W$. Our result can be seen as a polyhedral analogue of several classical and recent results related to the Frobenius problem. Our result is motivated by a large class of nonlinear integer optimization problems in variable dimension. Concretely, we aim to optimize $f(Wx)$ over a set $\mathcal{F} = P\cap \mathbb{Z}^n$, where $f$ is a nonlinear function, $P\subset \mathbb{R}^n$ is a polyhedron, and $W\in \mathbb{Z}^{d\times n}$. As a consequence of our representation theorem, we obtain a general efficient transformation from the latter class of problems to integer linear programming. Our bounds depend polynomially on various important parameters of the input data leading, among others, to first polynomial time algorithms for several classes of nonlinear optimization problems. Read More: http://epubs.siam.org/doi/10.1137/14M0973694

Item Type: Article
Date Type: Published Online
Status: Published
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Publisher: Society for Industrial and Applied Mathematics
ISSN: 0895-4801
Date of First Compliant Deposit: 30 March 2016
Date of Acceptance: 11 May 2015
Last Modified: 29 Jun 2019 22:17
URI: http://orca.cf.ac.uk/id/eprint/86767

Citation Data

Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item