Power engineering is concerned with the generation, transmission, and distribution
of electricity over electric power network. In this thesis, we focus on two operational
level optimization problems from power system planning, namely the Optimal Power
Flow Problem (OPF) and the Optimal Transmission Switching (OTS) Problem. The
former is a nonlinear network problem and the latter is the network design version of
the rst one. Due to nonlinearity induced by alternating current power
ow equations,
these two optimization problems, dened precisely in Chapter 1, are nonconvex and
require ecient global optimization methods.
In Chapter 2, we consider Alternating Current OPF (AC OPF) problem over
radial networks and analyze the approximation outcomes of the semidenite programming
(SDP) relaxation, which is proven to be exact over radial networks under
some technical conditions. We design a library of instances that demonstrate positive
SDP optimality gaps when these conditions do not hold. Finally, we propose valid
inequalities and variable bound tightening techniques that signicantly improve the
computational performance of a global optimization solver. Our work demonstrates
the need of developing ecient global optimization methods for the solution of OPF
even in the simple but fundamental case of radial networks.
In Chapter 3, we focus on the solution of AC OPF problem for the general case of
meshed networks. This chapter proposes three strong second-order cone programming
(SOCP) relaxations for the AC OPF problem by exploiting the underlying network
structure. Two of these three relaxations are incomparable to the standard SDP
relaxation of OPF. Extensive computational experiments show that these relaxations
have numerous advantages over existing convex relaxations in the literature in terms of
both quality of the relaxations and practicability to obtain feasible solutions within
a time framework that is compatible with the real-time operations in the current
industry practice.
In Chapter 4, we again consider the AC OPF problem with a particular emphasis
on solving more challenging instances. We analyze the properties of the minors
and submatrices of the matrix variable in a lifted formulation, and obtain a stronger
SOCP relaxation than the ones proposed in Chapter 3 by the addition of valid inequalities
and improved bound tightening techniques. We also propose an SOCP
based spatial branch-and-cut algorithm to solve the most dicult instances. Overall,
our methodology provides a computationally tractable approach to obtain strong
relaxation bounds for some of the hardest OPF instances from the literature.
In Chapter 5, we consider the so-called Direct Current OTS problem, which incorporates
a linear approximation to nonconvex AC power
ow equations. Most research
on DC OTS has focused on heuristic algorithms for generating quality solutions. However,
the mathematical theory of the DC OTS problem is less well-developed. In this
chapter, we formally establish that DC OTS is NP-Hard. We characterize the convex
hull of a cycle-induced relaxation inspired by Kircho's Voltage Law, and this
characterization provides strong valid inequalities that can be used in a cutting-plane
approach to solve the DC OTS. We give details of a practical implementation, and
show promising computational results on standard benchmark instances.
In Chapter 6, we focus on the OTS problem with the full AC power
ow model
since the commonly-used DC approximation of the power
ow model is known to
result in inaccurate
ow solutions. In this chapter, we propose a new exact formulation
for AC OTS and its mixed-integer second-order cone programming (MISOCP)
relaxation. We improve this relaxation via several types of strong valid inequalities
inspired by the developments for the AC OPF problem in Chapter 3. We also propose
a practical algorithm to obtain high quality feasible solutions for the AC OTS
problem. Extensive computational experiments show that the proposed formulation
and algorithms lead to signicant cost benets with provably tight bounds. |