Random Chemistry (RC)

A bare-bones implementation of the 'Random Chemistry' (RC) algorithm for finding a defective set.

This is a bare-bones implementation of the 'Random Chemistry' (RC) algorithm for finding a defective set from a universal set of N elements in log(N) trials. Multiple calls to this function comprise statistically independent trials.

Included with the algorithm implementation are a dummy fitness function and 'defective sets' to test the algorithm. See the accompanying algorithm, 'Sampling Inspired by Group Hyperedge Testing' (SIGHT), which can also be used to find defective sets in log(N) trials. SIGHT uses the same dummy fitness function and defective sets, for easy comparison, and is available on the File Exchange at: https://www.mathworks.com/matlabcentral/fileexchange/72718-sampling-inspired-by-group-hyperedge-testing-sight. Both algorithms have been successfully applied to identify small sets of transmission lines whose simultaneous failures cause cascading blackouts in power grid simulations (see reference below).

DISCLAIMER: This implementation is designed to be easy to read and understand, but is NOT optimized for efficiency and omits all the book-keeping and options under development that are contained in our working code. This should really be viewed as readable pseudo-code that runs.

COPYRIGHT: Laurence A. Clarfeld and Margaret J. Eppstein, Department of Computer Science, Univ. of Vermont
DATE: 8/26/2019

You are free to use or modify this code for research purposes, as long as you reference the website where you obtained the code.
IF YOU PUBLISH ANYTHING USING THIS CODE OR ALGORITHM, PLEASE REFERENCE THE FOLLOWING PAPERS:

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.

3. Clarfeld, L.A., and Eppstein, M.J. "Group-Testing on Hypergraphs with Variable-Cost Tests: A Power Systems Case Study", arXiv:1909.04513 [physics.soc-ph] (Preprint). September 9, 2019. Available from: https://arxiv.org/abs/1909.04513