UC Berkeley

This dissertation is concerned with the design of branch-and-cut algorithms for a variety of nonconvex nonlinear problems pertaining to power systems operations and planning. By understanding the structure of specific problems, we can leverage powerful commercial optimization solvers designed for convex optimization and mixed-integer programs. The bulk of the work concerns the Alternating Current Optimal Power Flow (ACOPF) problem. The ACOPF problem is to find a minimum cost generation dispatch that will yield flows that can satisfy demand as well as various engineering constraints. A standard formulation can be posed as a nonconvex Quadratically Constrained Quadratic Program with complex variables. We develop a novel spatial branch-and-bound algorithm for generic nonconvex QCQP with bounded complex variables that relies on a semidefinite programming (SDP) relaxation strengthened with linear valid inequalities. ACOPF-specific domain reduction or bound tightening techniques are also introduced to improve the algorithm's convergence rate. We also introduce second-order conic valid inequalities so that any SDP can be outer-approximated with conic quadratic cuts and test the technique on ACOPF. Another application is the incorporation of convex quadratic costs in unit commitment, which is a multi-period electric generation scheduling problem. We show that conic reformulation can both theoretically and practically improve performance on this mixed-integer nonlinear problem. We conclude with methods for approximating a mixed-integer convex exponential constraint. Applications include capital budgeting, the system reliability redundancy problem, and feature subset selection for logistic regression.