Mowen Lu

Harsha Nagarajan, Mowen Lu, Site Wang et al.

In this work, we develop an adaptive, multivariate partitioning algorithm for solving mixed-integer nonlinear programs (MINLP) with multi-linear terms to global optimality. This iterative algorithm primarily exploits the advantages of piecewise polyhedral relaxation approaches via disjunctive formulations to solve MINLPs to global optimality in contrast to the conventional spatial branch-and-bound approaches. In order to maintain relatively small-scale mixed-integer linear programs at every iteration of the algorithm, we adaptively partition the variable domains appearing in the multi-linear terms. We also provide proofs on convergence guarantees of the proposed algorithm to a global solution. Further, we discuss a few algorithmic enhancements based on the sequential bound-tightening procedure as a presolve step, where we observe the importance of solving piecewise relaxations compared to basic convex relaxations to speed-up the convergence of the algorithm to global optimality. We demonstrate the effectiveness of our disjunctive formulations and the algorithm on well-known benchmark problems (including Pooling and Blending instances) from MINLPLib and compare with state-of-the-art global optimization solvers. With this novel approach, we solve several large-scale instances which are, in some cases, intractable by the global optimization solver. We also shrink the best known optimality gap for one of the hard, generalized pooling problem instance.

Mowen Lu, Harsha Nagarajan, Emre Yamangil et al.

In recent years, there have been increasing concerns about how geomagnetic disturbances (GMDs) impact electrical power systems. Geomagnetically-induced currents (GICs) can saturate transformers, induce hot spot heating and increase reactive power losses. These effects can potentially cause catastrophic damage to transformers and severely impact the ability of a power system to deliver power. To address this problem, we develop a model of GIC impacts to power systems that includes 1) GIC thermal capacity of transformers as a function of normal Alternating Current (AC) and 2) reactive power losses as a function of GIC. We use this model to derive an optimization problem that protects power systems from GIC impacts through line switching, generator redispatch, and load shedding. We employ state-of-the-art convex relaxations of AC power flow equations to lower bound the objective. We demonstrate the approach on a modified RTS96 system and the UIUC 150-bus system and show that line switching is an effective means to mitigate GIC impacts. We also provide a sensitivity analysis of optimal switching decisions with respect to GMD direction.

Mowen Lu, Harsha Nagarajan, Russell Bent et al.

Since the alternating current optimal power flow (ACOPF) problem was introduced in 1962, developing efficient solution algorithms for the problem has been an active field of research. In recent years, there has been increasing interest in convex relaxations-based solution approaches that are often tight in practice. Based on these approaches, we develop tight piecewise convex relaxations with convex-hull representations, an adaptive, multivariate partitioning algorithm with bound tightening that progressively improves these relaxations and, given sufficient time, converges to the globally optimal solution. We illustrate the strengths of our algorithm using benchmark ACOPF test cases from the literature. Computational results show that our novel algorithm reduces the best-known optimality gaps for some hard ACOPF cases.

Kaarthik Sundar, Harsha Nagarajan, Sidhant Misra et al.

This article develops a strengthened convex quadratic convex (QC) relaxation of the AC Optimal Power Flow (AC-OPF) problem and presents an optimization-based bound-tightening (OBBT) algorithm to compute tight, feasible bounds on the voltage magnitude variables for each bus and the phase angle difference variables for each branch in the network. Theoretical properties of the strengthened QC relaxation that show its dominance over the other variants of the QC relaxation studied in the literature are also derived. The effectiveness of the strengthened QC relaxation is corroborated via extensive numerical results on benchmark AC-OPF test networks. In particular, the results demonstrate that the proposed relaxation consistently provides the tightest variable bounds and optimality gaps with negligible impacts on runtime performance.

Harsha Nagarajan, Mowen Lu, Emre Yamangil et al.

In this work, we propose a two-stage approach to strengthen piecewise McCormick relaxations for mixed-integer nonlinear programs (MINLP) with multi-linear terms. In the first stage, we exploit Constraint Programing (CP) techniques to contract the variable bounds. In the second stage we partition the variables domains using a dynamic multivariate partitioning scheme. Instead of equally partitioning the domains of variables appearing in multi-linear terms, we construct sparser partitions yet tighter relax- ations by iteratively partitioning the variable domains in regions of interest. This approach decouples the number of partitions from the size of the variable domains, leads to a significant reduction in computation time, and limits the number of binary variables that are introduced by the partitioning. We demonstrate the performance of our algorithm on well-known benchmark problems from MINLPLIB and discuss the computational benefits of CP-based bound tightening procedures.