A local relaxation approach for the siting of electrical substations.

*(English)*Zbl 1104.90032Summary: 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 \({\mathbf 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:

90C10 | Integer programming |

PDF
BibTeX
XML
Cite

\textit{W. Murray} and \textit{U. V. Shanbhag}, Comput. Optim. Appl. 33, No. 1, 7--49 (2006; Zbl 1104.90032)

Full Text:
DOI

##### References:

[1] | OQNP and MSDLP, User’s Manual, Optimal Methods Inc. and OptTek System Inc. |

[2] | R.N. Adams and M.A. Laughton, Static and time phased network synthesis, Proc. IEE, vol. 121, pp. 139–147, 1974. |

[3] | R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall: Englewood Cliffs, NJ, 1993. · Zbl 1201.90001 |

[4] | H.M. Amir and T. Hasegawa, ”Nonlinear mixed-discrete structural optimization,” Journal of Structural Engineering, vol. 115, pp. 626–646, 1989. |

[5] | J.Z. Cha and R.W. Mayne, ”Optimization with discrete variables via recursive quadratic programming: Part 2 - algorithms and results,” Transactions of the ASME, Journal of Mechanisms, Transmissions and Automation in Design, vol. 111, pp. 130–136, 1989. |

[6] | D.M. Crawford and S.B. Holt, ”A mathematical optimization technique for locating and sizing distribution substations and deriving their optimal service areas,” IEEE Transactions on PAS, pp. 230–235, 1975. |

[7] | M. Duran and I. Grossmann, ”An outer-approximation algorithm for a class of mixed-integer nonlinear programs,” Mathematical Programming, vol. 36, pp. 307–339, 1986. · Zbl 0619.90052 |

[8] | M.A. El-Kady, ”Computer-aided planning of distribution substation and primary feeders,” IEEE Transactions on PAS, vol. PAS-103, pp. 1183–1192, 1984. |

[9] | A.M. Geoffrion, ”Generalized benders decomposition,” J. Optim. Theory Appl,, vol. 10, pp. 237–260, 1972. · Zbl 0229.90024 |

[10] | P.E. Gill, W. Murray, and M.A. Saunders, SNOPT: An SQP algorithm for large-scale constrained optimization, Tech. Report NA–97–2, Systems Optimization Laboratory, Stanford University, San Diego, CA, 1997. · Zbl 1210.90176 |

[11] | User’s guide for SQOPT 5.3: A Fortan package for large-scale linear and quadratic programming, tech. report, Systems Optimization Laboratory, Department of Operations Research, Stanford University - 94305-4022, 1997. |

[12] | G.H. Golub and C.F. Vanloan, ”Unsymmetric positive definite linear systems,” Linear Algebra and Its Applications, vol. 28 pp. 85–98, 1979. · Zbl 0419.65025 |

[13] | K.S. Hindi and A. Brameller, ”Design of low-voltage distribution networks: a mathematical programming method,” Proc. IEE, vol. 124, pp. 54–58. 1977. |

[14] | K. Holmstrom, ”The TOMLAB Optimization Environment in Matlab,” Advanced Modeling and Optimization, vol. 1, pp. 47–69. 1999. · Zbl 1115.90404 |

[15] | U.G.W. Knight, ”The logical design of electricity networks using linear programming methods,” Proc. IEE, vol. 117, pp. 2117–2127. 1970. |

[16] | S. Leyffer, Deterministic Methods for Mixed Integer Nonlinear Programming, PhD thesis, University of Dundee, Dundee, Scotland, UK, 1993. |

[17] | A.C. Marshall, T.B. Boffy, J.R. Green, and H. Hague, ”Optimal design of electricity networks,” IEEE Proceedings-C, vol. 138, pp. 69–77. 1991. |

[18] | E. Masud, ”An interactive procedure for sizing and timing distribution substations using optimization techniques,” IEEE Trans. on PAS, vol. 93, pp. 1281–1286. 1974. |

[19] | J.J. More and S.J. Wright, Optimization software guide, part 2, pp 87–89, SIAM Philadelphia, 1993. |

[20] | G.L. Nemhauser and L.A. Wolsey, ”Integer and Combinatorial Optimization,” John Wiley, New York, 1988. · Zbl 0652.90067 |

[21] | A. Neumaier, O. Shcherbina, W. Huyer, and T. Vinko, ”A comparison of complete global optimization solvers,” Mathematical Programming, Series B., vol. 103, pp. 333–356. 2004. · Zbl 1099.90001 |

[22] | K.-M. Ng, A Continuation Approach to Solving Continuous Problems with Discrete Variables, PhD thesis, Stanford University, Stanford, CA 94305, June, 2002. |

[23] | G.R. Olsen and G.N. Vanderplaats, ”Methods for nonlinear optimization with discrete design variables,” AIAA Journal, vol. 27, pp. 1584–1589, 1989. |

[24] | N.V. Sahinidis and M. Tawarmalani, ”Baron 7.2: Global Optimization of Mixed-Integer Nonlinear Programs,” User’s Manual, 2004. · Zbl 1062.90041 |

[25] | S. Sharif, M. Salamat, and A. Vanelli, ”Model for future expansion of radial distribution networks using mixed integer programming,” IEEE, pp. 152–155, 1996. |

[26] | M. Tawarmalani and N.V. Sahinidis, ”Global optimization of mixed-integer nonlinear programs: A theoretical and computational study,” Mathematical Programming, vol. 99, pp. 563–591. 2004. · Zbl 1062.90041 |

[27] | G.L. Thompson and D.L. Wall, ”A branch and bound model for choosing optimal substation locations,” IEEE Transactions on PAS,, PAS-100 pp. 2683–2687, 1981. |

[28] | D.L. Wall, G.L. Thompson, and J.E.D. Northcote-Green, ”An optimization model for planning radial distribution networks,” IEEE Transactions on PAS, PAS-98 pp. 1061–1066. 1979. |

[29] | H.L. Willis, H. Tram, M.V. Engel, and L. Finley, ”Optimization applications to distribution,” IEEE Computer Applications in Power, vol. 10, pp. 12–17, 1995. |

[30] | H.L. Willis, H. Tram, M.V. Engel and L. Finley, ”Selecting and applying distribution optimization methods,” IEEE Computer Applications in Power, vol. 1, pp. 12–17, 1996. |

[31] | S.J. Wright, Primal-Dual Interior-Point Methods, SIAM, 1996. · Zbl 0863.65031 |

[32] | K. Yahav and G. Oron, ”Optimal locations of electrical substations in regional energy supply systems,” IEEE, pp. 307–310, 1996. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.