Canonical Cuts on the Unit Hypercube

Authors:
  • EBEgon Balas
    Egon Balas
  • RJRobert Jeroslow
    Robert Jeroslow

Abstract
In this paper we study some properties of the n-dimensional unit hypercube K. We define a distance function on the set V of vertices of K, and use it to construct a class of hyperplanes parallel to the faces of K (canonical hyperplanes). We then establish some properties of these hyperplanes and of the associated canonical inequalities (cuts), and we show that adjacent canonical inequalities imply stronger canonical cuts. An arbitrary inequality is shown to imply a set of canonical cuts such that a vertex of K satisfies the arbitrary inequality if and only if it satisfies the set of implied canonical cuts (Theorem 2). As a consequence of this, we show that every bounded integer program can be stated as a set covering problem (Corollary 2.1). The above results (with the exception of Corollary 2.1, which was added later) were first stated in [1], and a brief note on them was published in [2]. For background material and related concepts the reader is referred to [3].