Selecting Constraints Rather Than Vertices

The simplest example of Attic in a three-dimensional space consists of an ordinary room with a parallel floor and roof as well as parallel pairs of side lateral walls. Within this simple Attic there are three (like the space dimensions) couples of mutually incompatible constraints. It is easy to generalize this problem the ny dimensions can be larger than 3 complementary constraints can be nonparallel on condition that they do not meet each other within the feasible region distances between opposite vertices in the complementary constraints can be different, but not zero. 

The following features characterize this speciflc class of attics, but it is worth accounting for them for more general classes also  

A two-level factorial allows this class of attics to be represented quite simply — and -I- are the complementary constraints. 

The Klee-Minty problem is a typical example of this class of problem where — is the nonnegativity constraint and -t- is the complementary constraint used to obtain a variable. 

In the three-dimensional case, the possible combinations (vertices) of active constraints for the Klee-Minty problem are 2 = 2 = 8 and, by sorting them from the smallest objective function value, the result is (columns = constraints rows = vertices) 

---