The integer hull of a convex rational polytope (Q701781): Difference between revisions

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\).