More Like this

1. Minimum-Time Charging of Energy Storage in Microgrids via Approximate Conic Relaxation

   https://doi.org/10.23919/ECC51009.2020.9143992  

   Guthrie, James; Mallada, Enrique (May 2020, 2020 European Control Conference)

   null (Ed.)

   We study the problem of maximizing energy transfer to a load in a DC microgrid while respecting constraints on bus voltages and currents, and accounting for the impact of neighboring constant power loads. Both the objective and dynamics give rise to indefinite quadratic terms, resulting in a non-convex optimization problem. Through change of variables and relaxations we develop a closely related second-order cone program. The problem retains the same feasible set as the original problem but utilizes a linear approximation of the non-convex objective. We demonstrate how this can be used to design approximately optimal charging profiles for periodic pulsed loads in real time. 

   more » « less
2. Minimum-time charging of energy storage in microgrids via approximate conic relaxation

   Guthrie, James; Mallada, Enrirque (May 2020, European Control Conference)

   We study the problem of maximizing energy transfer to a load in a DC microgrid while respecting constraints on bus voltages and currents, and accounting for the impact of neighboring constant power loads. Both the objective and dynamics give rise to indefinite quadratic terms, resulting in a non-convex optimization problem. Through change of variables and relaxations we develop a closely related second-order cone program. The problem retains the same feasible set as the original problem but utilizes a linear approximation of the non-convex objective. We demonstrate how this can be used to design approximately optimal charging profiles for periodic pulsed loads in real time. 

   more » « less
3. Submodularity in Conic Quadratic Mixed 0–1 Optimization

   https://doi.org/10.1287/opre.2019.1888  

   Atamtürk, Alper; Gómez, Andrés (January 2020, Operations Research)

   We describe strong convex valid inequalities for conic quadratic mixed 0–1 optimization. These inequalities can be utilized for solving numerous practical nonlinear discrete optimization problems from value-at-risk minimization to queueing system design, from robust interdiction to assortment optimization through appropriate conic quadratic mixed 0–1 relaxations. The inequalities exploit the submodularity of the binary restrictions and are based on the polymatroid inequalities over binaries for the diagonal case. We prove that the convex inequalities completely describe the convex hull of a single conic quadratic constraint as well as the rotated cone constraint over binary variables and unbounded continuous variables. We then generalize and strengthen the inequalities by incorporating additional constraints of the optimization problem. Computational experiments on mean-risk optimization with correlations, assortment optimization, and robust conic quadratic optimization indicate that the new inequalities strengthen the convex relaxations substantially and lead to significant performance improvements. 

   more » « less
4. Determinant Maximization via Matroid Intersection Algorithms

   Brown, A; Laddha, A.; Pittu, M.; Singh, M.; Tetali, P. (October 2022, Annual Symposium on Foundations of Computer Science)

   Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics [Puk06], convex geometry [Kha96], fair allocations [AGSS16], combinatorics [AGV18], spectral graph theory [NST19a], network design, and random processes [KT12]. In an instance of a determinant maximization problem, we are given a collection of vectors U = {v1, . . . , vn} ⊂ Rd , and a goal is to pick a subset S ⊆ U of given vectors to maximize the determinant of the matrix ∑i∈S vivi^T. Often, the set S of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint (|S| ≤ k) or matroid constraint (S is a basis of a matroid defined on the vectors). In this paper, we give a polynomial-time deterministic algorithm that returns a r O(r)-approximation for any matroid of rank r ≤ d. This improves previous results that give e O(r^2)-approximation algorithms relying on e^O(r)-approximate estimation algorithms [NS16, AG17,AGV18, MNST20] for any r ≤ d. All previous results use convex relaxations and their relationship to stable polynomials and strongly log-concave polynomials. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the det(.) function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm. 

   more » « less
5. Fast LP-based Approximations for Geometric Packing and Covering Problems

   Chekuri, Chandra; Har-Peled, Sariel; Quanrud, Kent (January 2020, Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms)

   We derive fast approximation schemes for LP relaxations of several well-studied geometric optimization problems that include packing, covering, and mixed packing and covering constraints. Previous work in computational geometry concentrated mainly on the rounding stage to prove approximation bounds, assuming that the underlying LPs can be solved efficiently. This work demonstrates that many of those results can be made to run in nearly linear time. In contrast to prior work on this topic our algorithms handle weights and capacities, side constraints, and also apply to mixed packing and covering problems, in a unified fashion. Our framework relies crucially on the properties of a randomized MWU algorithm of [41]; we demonstrate that it is well-suited for range spaces that admit efficient approximate dynamic data structures for emptiness oracles. Our framework cleanly separates the MWU algorithm for solving the LP from the key geometric data structure primitives, and this enables us to handle side constraints in a simple way. Combined with rounding algorithms that can also be implemented efficiently, we obtain the first near-linear constant factor approximation algorithms for several problems. 

   more » « less