A local relaxation approach for the siting of electrical<br/><br/>substations

Wednesday, November 19, 2008 - 11:15am - 12:00pm
EE/CS 3-180
Uday Shanbhag (University of Illinois at Urbana-Champaign)
Joint work with Walter Murray (Stanford University).

The siting and sizing of electrical substations on a rectangular electrical grid can be formulated
as an integer programming problem with a quadratic objective and linear constraints. We propose a novel
approach that is based on solving a sequence of local relaxations of the problem for a given number of
substations. Two methods are discussed for determining a new location from the solution of the relaxed
problem. Each leads to a sequence of strictly improving feasible integer solutions. The number of substations
is then modified to seek a further reduction in cost. Lower bounds for the solution are also provided by solving
a sequence of mixed-integer linear programs. Results are provided for a variety of uniform and Gaussian load
distributions as well as some real examples from an electric utility. The results of GAMS/DICOPT, GAMS/SBB,
GAMS/BARON and CPLEX applied to these problems are also reported. Our algorithm shows slow growth in
computational effort with the number of integer variables.

MSC Code: