Random Chemistry Algorithm

Random Chemistry (RC) finds a minimal subset that has some desired property in O(log N) time.

The Random Chemistry algorithm rapidly finds one minimal 'positive' subset with between 2 and a pre-specified number of elements, from within an N-element universal set, in only O(log N) computation time. Multiple calls to this algorithm comprise statistically independent trials, so can be used as an unbiased sampling methods for finding many such minimal 'positive' subsets. The definition of a 'positive' subset is application dependent. For example, we use this to find which subsets of component outages in an electrical grid will trigger a cascading failure.
RClight.m is an easy-to-read version of the basic RC algorithm. We have deliberately removed optimizations that use auxiliary data structures and a variety of options (such as different set size reduction schedules, different sampling strategies, etc.) to keep the code simple and understandable so that it can be easily modified for your purposes.

We have also included a dummy boolean fitness function that returns whether or not a subset is 'positive', based on whether it is included in a pre-specified list of 'positive' subsets that are stored in the file positivesubsets.mat. A sample call using this dummy function is shown below and in the internal documentation:
positivesubset = RClight(2896,80,5,20,@useknownlist)
where 2896 is the universal set size, 80 is the size of the initial subset to try, 5 is the maximum minimal subset size desired, 20 is the number of times to search for a subset of a given size, and useknownlist is the name of the dummy fitness function that determines whether a subset is 'positive' (its included at the bottom of the RClight.m file).

If you use this code please reference this website and also reference the following two papers (RClight follows the pseudo-code described in ref 1 below, with the exception that in Step 3 it uses the bottom-up approach for the final search as described in ref 2 below).

1. Eppstein, Margaret J., and Paul DH Hines. "A “random chemistry” algorithm for identifying collections of multiple contingencies that initiate cascading failure." IEEE Transactions on Power Systems 27.3 (2012): 1698-1705.

2.Rezaei, Pooya, Margaret J. Eppstein, and Paul DH Hines. "Rapid Assessment, Visualization, and Mitigation of Cascading Failure Risk in Power Systems." System Sciences (HICSS), 2015 48th Hawaii International Conference on. IEEE, 2015.