The number of feasible designs in a compatibility matrix

Many design and planning problems consist of a number of distinct subsystems. Generally, there are several possible alternatives for design of a subsystem. However, an alternative for one subsystem may be incompatible with an alternative for another subsystem. Thus, a feasible design is one that incorporates one alternative for each subsystem such that no pairwise incompatibilities exist. Several such design and planning problems have been formulated as compatibility matrices. The feasible designs can be identified by using an efficient algorithm. This paper shows that, in general, the exact number of feasible designs decreases exponentially with the increase in the number of incompatible pairs. This finding should motivate more potential users to employ the compatibility matrix approach.