Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00059
Statistical Analysis of Algorithms: A Case Study of Market-Clearing
Mechanisms in the Power Industry
Chris Barrett,
Achla Marathe,
Madhav Marathe,
Doug Cook,
Gregory Hicks,
Vance Faber,
Aravind Srinivasan,
Yoram Sussmann, and
Heidi Thornquist
Vol. 7, no. 1, pp. 3-31, 2003. Regular paper.
Abstract 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.
|
Journal Supporters
|