Computational Optimization and Applications, 33, 7–49, 2006c!2006 Springer Science + Business Media Inc. Manufactured in The Netherlands.DOI: 10.1007/s10589-005-5957-4A Local Relaxation Approach for the Sitingof Electrical SubstationsWALTER MURRAY∗[email protected] of Management Science and Engineering, Stanford University, Stanford, CA 94305-4026UDAY V. SHANBHAG [email protected] of Mechanical and Industrial Engineering, Urbana, IL 61801Received March 10, 2005; Revised June 27, 2005; Accepted July 6, 2005Abstract. The siting and sizing of electrical substations on a rectangular electrical grid can be formulatedas an integer programming problem with a quadratic objective and linear constraints. We propose a novelapproach that is based on solving a sequence of local relaxations of the problem for a given number ofsubstations. Two methods are discussed for determining a new location from the solution of the relaxedproblem. Each leads to a sequence of strictly improving feasible integer solutions. The number of substationsis then modified to seek a further reduction in cost. Lower bounds for the solution are also provided by solvinga sequence of mixed-integer linear programs. Results are provided for a variety of uniform and Gaussian loaddistributions as well as some real examples from an electric utility. The results ofGAMS/DICOPT, GAMS/SBB,GAMS/BARON and CPLEX applied to these problems are also reported. Our algorithm shows slow growth incomputational effort with the number of integer variables.1. IntroductionAn important planning problem faced by electric utilities concerns where to placenew substations to meet future electrical load. The planning objective is to minimizethe cost of new substations and the electrical losses when operating the system. Theconstraints include Kirchhoff’s law equations, voltage bounds and capacity boundson the current at substation nodes. The electrical load supported by the grid and thelinkage impedance are known. Kirchhoff’s law leads to constraints (called the load-flowequations) that relate the voltages and the currents at the nodes through the admittancematrix. The problem may be formulated as a mixed-integer programming problem with aquadratic objective and linear constraints. By introducing a novel relaxation, we attemptto solve such a problem by solving a sequence of quadratic programs with continuousvariables.The paper is organized into five sections. Section 2 discusses some of the earlyresearch in this area. Section 3 gives a formulation of the problem, while in Section 4our new algorithm is described. Section 5 describes different relaxations of the originalproblem that provide a means of obtaining an initial feasible solution and deriving lowerbounds on cost. Results of applying our new algorithm on a variety of test and realworld problems are given in section 6. To allow a comparison, Section 6 also givesthe results of applyingGAMS/DICOPT, GAMS/SBB and CPLEX to the smaller problems.∗To whom correspondence should be addressed.8 MURRAY AND SHANBHAGFigure 1. The substation siting optimization problem: The figure on the left shows the placement ofexisting or fixed substations and new substations. On the right, the load or current distribution on the grid isshown.The last section lists the contributions and conclusions of this study and proposes somefuture work.2. Past researchA useful introduction to the problem is provided in Willis et al. [29]. This referencediscusses the problem briefly and focuses on some specific aspects such as feeder layout,cable sizes and load distribution across the feeders and substations (figure 1). A secondpaper by the same authors [30] discusses the the variety of methods that can be used tosolve the problem. For example, transshipment algorithms convert the electrical networkproblem into one for which network flow algorithms can be applied.2.1. Transshipment methodsOne of the earliest references of an optimal planning approach toward the design ofelectrical networks is by Knight [15]. Based on a given set of geographical locations,a minimum cost network design was obtained using a network flow algorithm (Ahujaet al. [3] provide an excellent review of network flow algorithms). The objective functionaccounted for circuit length and apparent power and the constraints included securityand switchgear limitations. Similar approaches are also seen in the following references[6, 8, 13].In [28], Wall et al. use a transshipment algorithm to determine decisions conditionalon a choice of integer variables. A branch-and-bound algorithm selects the optimalsolution from the candidate solutions generated by the transshipment code. Capitalcosts are included for potential substations. Note that the essential problem formulationfor the transshipment code is similar to that used by Adams and Laughton [2]. The sameauthors present more details on the embedded transshipment algorithm in [27].Sharif et al. [25] give an algorithm that used both mixed integer linear programming(MIP) and spanning tree methods to estimate future expansion paths for a radialLOCAL RELAXATION APPROACH 9distribution network. The general methodology comprises two steps: The first, thegeneration of spanning trees to connect the source to the demand nodes, and second, aMIP approach to ascertaining which spanning tree to use as the optimal solution.2.2. Non-transshipment algorithmsEl-Kady [8] modeled the planning of distribution substations and associated feedersover time. Marshall et al. [17] solved a distribution planning problem by a slight mod-ification in the objective function. The costs in this particular methodology arose fromcabling, switchgear and the incremental costs of building an extra circuit to a loadnode. This ensures that every load point has some security of supply; if one circuitgoes down, another supplies it with power. The cost of losses was not included inthis study. Provisions were made to ensure the security of the network. The solutionmethodology adopted is that of maximizing the Lagrangian dual using the NETOPTprogram.Yahav and Oron [32] accounted for the nonlinear costs of losses and constructionthrough the solution of a nonlinear program using the off-the-shelf solver GINO (it usesthe generalized reduced gradient solver GRG2 by Lasdon and Waren [19]. New feederroutes and substation locations are the optimal decisions of the mathematical program.Amongst the more restrictive assumptions made are the