Statistical Analysis of Algorithms: A Case Study of Market-Clearing Mechanisms in the Power Industry

We carry out a detailed empirical analysis of simple heuristics and provable algorithms for bilateral contract-satisfaction problems. Such problems arise due to the proposed deregulation of the electric utility industry in the USA. Given a network and a (multi)set of pairs of vertices (contracts) with associated demands, the goal is to find the maximum number of simultaneously satisfiable contracts. Four different algorithms (three heuristics and a provable approximation algorithm) are considered and their performance is studied empirically in fairly realistic settings using rigorous statistical analysis. For this purpose, we use an approximate electrical transmission network in the state of Colorado. Our experiments are based on the statistical technique Analysis of Variance (ANOVA), and show that the three heuristics outperform a theoretically better algorithm. We also test the algorithms on four types of scenarios that are likely to occur in a deregulated marketplace. Our results show that the networks that are adequate in a regulated marketplace might be inadequate for satisfying all the bilateral contracts in a deregulated industry. Communicated by Dorothea Wagner: submitted April 2002; revised December 2002. C. Barrett et al., Statistical Analysis of Algorithms , JGAA, 7(1) 3–31 (2003) 4