\(k\)-integrality, an extension of total unimodularity (Q688932)

The author considers a matrix \(A\) of integers and a vector \(b\) of integers such that all the elements of \(b\) have a common divisor \(k\). He gives a necessary and sufficient condition for the polyhedron \(P(a,b)\), where \(P(a,b)=\{x\mid x\geq 0,\;Ax\leq b\}\), to have only integral extreme points. These conditions refer to elements of inverse matrices of all bases derived from \(A\), and they are an extension of the classical theory of total unimodularity to \(k\)-integrability. A special version is provided for the case where \(k\) is a prime number. For \(k=2\) applications of this result are shown for the obnoxious facility location problem [see the author and \textit{I. Giannikos}, J. Oper. Res. Soc., to appear] and for ternary covering and packing problems.