The integer hull of a convex rational polytope
type: Item
instance of: scholarly article
title: The integer hull of a convex rational polytope
zbMATH Open document ID: 1059.52021
published in: Discrete \& Computational Geometry
publication date: 2004-12-16T00:00:00Z
review text: For \(A\in Z^{m\times n}\), \(b\in Z^m\), \(x\in\mathbb{R}^n\) the integer program \[ \max \{c'x:Ax=b,x\in N^n\} \] with a compact convex polyhedron \(Ax=b\), \(x\geq 0\), is investigated. If \(P_i\) denotes the integer hull of that polyhedron, then solving the integer program above is equivalent to solving the linear program \(\max\{ c'x:x\in P_i\}\). The paper is motivated by the fact that finding the integer hull of \(Ax=b\) is a difficult problem, since no explicit (or ``simple'') characterization or description of \(P_i\) in terms of the initial data \(A\) and \(b\) is known so far. Based on this, the author provides a structural result on the integer hull \(P_i\) of a convex rational polyhedron giving an explicit algebraic characterization of the defining hyperplanes of \(P_i\), in terms of generators of a certain convex cone \(C\), where \(C\) is described directly from the initial data, with no calculation. In the sense described above, also an explicit linear program \(\max\{\widehat c'q:Mq=r,q\geq 0\}\) equivalent to the integer program \(\max\{c'x:Ax =b,x\in N^n\}\) is provided, where \(M,r,\widehat c'\) are easily obtained from \(A,b,c\).
reviewed by: Horst Martini
Mathematics Subject Classification ID: 52B20
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 2123186
zbMATH Keywords: integer program
zbMATH Keywords: linear program
zbMATH Keywords: discrete Farkas lemma
zbMATH Keywords: binomial ideal
zbMATH Keywords: lifting
author: Jean B. Lasserre
MaRDI profile type: Publication
full work available at URL: s00454-003-0834-3
OpenAlex ID: W2034285985
DOI: 10.1007/S00454-003-0834-3
Recommended article: The Integer Hull of a Convex Rational Polytope
Recommended article: Computing the integer hull of convex polyhedral sets
Recommended article: Upper and lower bound results on the convex hull of integer points in polyhedra
Recommended article: On Counting Integral Points in a Convex Rational Polytope
Recommended article: An upper bound theorem for rational polytopes
Recommended article: The Convex Hull of Rational Plane Curves
Recommended article: On integer points in polyhedra
Recommended article: Q4011309
Recommended article: Integer hulls of linear polyhedra and scl in families
description: scientific article; zbMATH DE number 2123186