Harsha Nagarajan

The alternating current optimal transmission switching (ACOTS) problem incorporates line switching decisions into the alternating current optimal power flow framework, offering well-known benefits in reducing operational costs and enhancing system reliability. ACOTS optimization models contain discrete variables and nonlinear, nonconvex constraints, which make them difficult to solve. In this work, we develop strengthened quadratic convex (QC) relaxations for ACOTS, in which we tighten the relaxation with several new valid inequalities, including a novel kind of on/off cycle–based polynomial constraints by taking advantage of the network structure. We linearize the sum of on/off trilinear terms in the relaxation using extreme-point representation, demonstrating theoretical tightness, and efficiently incorporate on/off cycle–based polynomial constraints through disjunctive programming–based cutting planes. Combined with an optimization-based bound-tightening algorithm, this results in the tightest QC-based ACOTS relaxation to date. We additionally propose a novel maximum spanning tree–based heuristic to improve the computational performance by fixing certain lines to be switched on. Our extensive numerical experiments on medium-scale power grid library instances show significant improvements on relaxation bounds, whereas tests on large-scale instances with up to 2,312 buses demonstrate substantial performance gains. To our knowledge, this is the first ACOTS relaxation-based approach to demonstrate near-optimal switching solutions on realistic large-scale power grid instances. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: The authors gratefully acknowledge support from the U.S. Department of Energy through Los Alamos National Laboratory’s directed research and development program [Grant 20230091ER: Learning to Accelerate Global Solutions for Non-Convex Optimization]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0236 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0236 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

We present a depth-aware optimization framework for quantum circuit compilation that unifies provable optimality with scalable heuristics. For exact synthesis of a target unitary, we formulate a mixed-integer linear program (MILP) that linearly handles global-phase equivalence and uses explicit parallel scheduling variables to certify depth-optimal solutions for small-to-medium circuits. Domain-specific valid constraints, including identity ordering, commuting-gate pruning, short-sequence redundancy cuts, and Hermitian-conjugate linkages, significantly accelerate branch-and-bound, yielding speedups up to 43x on standard benchmarks. The framework supports hardware-aware objectives, enabling fault-tolerant (e.g. T-count) and NISQ-era (e.g. entangling gates) devices. For approximate synthesis, we propose 3 objectives: (i) exact, but non-convex, phase-invariant fidelity maximization; (ii) a linear surrogate that maximizes the real trace overlap, yielding a tight lower bound to fidelity; and (iii) a convex quadratic function that minimizes the circuit's Frobenius error. To scale beyond exact MILP, we propose a novel rolling-horizon optimization (RHO) that rolls primarily in time, caps the active-qubits, and enforces per-qubit closure while globally optimizing windowed segments. This preserves local context, reduces the Hilbert-space dimension, and enables iterative improvements without ancillas. On a 142-gate seed circuit, RHO yields 116 gates, an 18.3% reduction from the seed, while avoiding the trade-off between myopic passes and long run times. Empirically, our exact compilation framework achieves certified depth-optimal circuits on standard targets, high-fidelity Fibonacci-anyon weaves, and a 36% gate-count reduction on multi-body parity circuits. All methods are in the open-source QuantumCircuitOpt, providing a single framework that bridges exact certification and scalable synthesis.

We learn optimal instance-specific heuristics for the global minimization of nonconvex quadratically constrained quadratic programs (QCQPs). Specifically, we consider partitioning-based convex mixed-integer programming relaxations for nonconvex QCQPs and propose the novel problem of strong partitioning to optimally partition variable domains without sacrificing global optimality. Because solving this max-min strong partitioning problem exactly can be very challenging, we design a local optimization method that leverages generalized gradients of the value function of its inner-minimization problem. However, even solving the strong partitioning problem to local optimality can be time consuming. To address this, we propose a simple and practical machine learning (ML) approximation for homogeneous families of QCQPs. Motivated by practical applications, we conduct a detailed computational study using the open-source global solver Alpine to evaluate the effectiveness of our ML approximation in accelerating the repeated solution of homogeneous QCQPs with fixed structure. Our study considers randomly generated QCQP families, including instances of the pooling problem, that are benchmarked using state-of-the-art global optimization software. Numerical experiments demonstrate that our ML approximation of strong partitioning reduces Alpine’s solution time by a factor of 2–4.5 on average, with maximum reduction factors ranging from 10 to 200 across these QCQP families. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: The authors gratefully acknowledge funding from Los Alamos National Laboratory’s Center for Nonlinear Studies and the U.S. Department of Energy’s Laboratory Directed Research and Development program [Grants 20230091ER (Project “Learning to Accelerate Global Solutions for Non-convex Optimization”) and 20210078DR (Project “The Optimization of Machine Learning: Imposing Requirements on Artificial Intelligence”)]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0424 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0424 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

The software and data in this repository are a snapshot of the software and data that were used in the research reported in the paper by R. Kannan, H. Nagarajan, and D. Deka.

The goal of this repository is to demonstrate the efficiency and effectiveness of our strengthened Quadratic Convex (QC) relaxation formulation and algorithms for the AC Optimal Transmission Switching (ACOTS) problem.