Canonical Cuts on the Unit Hypercube
Egon Balas, Robert Jeroslow
Source 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].
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.