Description: |
VISOR: Vast independence system optimization routine.
An algorithm is sketched that generates all K maximal independent sets and all M minimal dependent sets of an arbitrary independence system, based on a set of cardinality n having at most 2 n subsets, with access to an oracle that decides if a set is independent or not. Because the algorithm generates all those sets, it solves the problems of finding all maximum independent and minimum dependent sets. Those problems are known to be impossible to solve in general in time polynomial in n, K, and M, and they are NP-hard. The algorithm proposed and used is efficient in the sense that it requires only O(nK+M) or O(K+nM) visits to the oracle, the nonpolynomial part is only related to bitstring comparisons and the like, which can be performed rather quickly and, to some degree, in parallel on a sequential machine. This complexity compares favorably with another algorithm that is O(n 2 K 2 ). The design of a computer routine that implements the algorithm in a highly optimized way is discussed. The routine behaves as expected, as is shown by numerical experiments on a range of randomly generated independence systems with n up to n=34. Application on an engineering design problem with n=28 shows the routine requires almost 10 6 times less visits to the oracle than an exhaustive search, while the time spent in visiting the oracle is still significantly larger than that spent for all other computations together. |