Search for: All records

Abstract A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective function subject to multiple two-sided linear inequalities intersected with a low-rank and spectral constrained domain. Although solving LSOP is generally NP-hard, its partial convexification (i.e., replacing the domain with its convex hull), termed “LSOP-R, is often tractable and yields a high-quality solution. This motivates us to study the strength of LSOP-R. Specifically, we derive rank bounds for any extreme point of LSOP-R in different matrix spaces and prove their tightness. The proposed rank bounds recover two well-known results in the literature from a fresh angle and allow us to derive sufficient conditions under which the relaxation LSOP-R is equivalent to LSOP. To effectively solve LSOP-R, we develop a column generation algorithm with a vector-based convex pricing oracle and a rank-reduction algorithm, which ensures that the output solution always satisfies the theoretical rank bound. Finally, we numerically verify the strength of LSOP-R and the efficacy of the proposed algorithms. 

Abstract Distributionally Favorable Optimization (DFO) is a framework for decision-making under uncertainty, with applications spanning various fields, including reinforcement learning, online learning, robust statistics, chance-constrained programming, and two-stage stochastic optimization without complete recourse. In contrast to the traditional Distributionally Robust Optimization (DRO) paradigm, DFO presents a unique challenge– the application of the inner infimum operator often fails to retain the convexity. In light of this challenge, we study the tractability and complexity of DFO. We establish sufficient and necessary conditions for determining when DFO problems are tractable (i.e., solvable in polynomial time) or intractable (i.e., not solvable in polynomial time). Despite the typical nonconvex nature of DFO problems, our results show that they are mixed-integer convex programming representable (MICP-R), thereby enabling solutions via standard optimization solvers. Finally, we numerically validate the efficacy of our MICP-R formulations. 

Abstract Urban air mobility (UAM) is an emerging air transportation mode to alleviate the ground traffic burden and achieve zero direct aviation emissions. Due to the potential economic scaling effects, the UAM traffic flow is expected to increase dramatically once implemented, and its market can be substantially large. To be prepared for the era of UAM, we study the fair and risk‐averse urban air mobility resource allocation model (FairUAM) under passenger demand and airspace capacity uncertainties for fair, safe, and efficient aircraft operations. FairUAM is a two‐stage model, where the first stage is the aircraft resource allocation, and the second stage is to fairly and efficiently assign the ground and airspace delays to each aircraft provided the realization of random airspace capacities and passenger demand. We show that FairUAM is NP‐hard even when there is no delay assignment decision or no aircraft allocation decision. Thus, we recast FairUAM as a mixed‐integer linear program (MILP) and explore model properties and strengthen the model formulation by developing multiple families of valid inequalities. The stronger formulation allows us to develop a customized exact decomposition algorithm with both benders and L‐shaped cuts, which significantly outperforms the off‐the‐shelf solvers. Finally, we numerically demonstrate the effectiveness of the proposed method and draw managerial insights when applying FairUAM to a real‐world network. 

In modeling battery energy storage systems (BESS) in power systems, binary variables are used to represent the complementary nature of charging and discharging. A conventional approach for these BESS optimization problems is to relax binary variables and convert the problem into a linear program. However, such linear programming relaxation models can yield unrealistic fractional solutions, such as simultaneous charging and discharging. In this paper, we develop a regularized mixed-integer programming (MIP) model for the optimal power flow (OPF) problem with BESS. We prove that, under mild conditions, the proposed regularized model admits a zero integrality gap with its linear programming relaxation; hence, it can be solved efficiently. By studying the properties of the regularized MIP model, we show that its optimal solution is also near optimal to the original OPF problem with BESS, thereby providing a valid and tight upper bound for the OPF problem with BESS. The use of the regularized MIP model allows us to solve a trilevel [Formula: see text]-[Formula: see text]-[Formula: see text] network contingency problem, which is otherwise intractable to solve. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: N. Jiang (as a graduate student at the Georgia Institute of Technology) and W. Xie were supported in part by the National Science Foundation [Grant 2246414] and the Office of Naval Research [Grant N00014-24-1-2066]. 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.2024.0771 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0771 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . 

Sparse principal component analysis (SPCA) is designed to enhance the interpretability of traditional principal component analysis by optimally selecting a subset of features that comprise the first principal component. Given the NP-hard nature of SPCA, most current approaches resort to approximate solutions, typically achieved through tractable semidefinite programs or heuristic methods. To solve SPCA to optimality, we propose two exact mixed-integer semidefinite programs (MISDPs) and an arbitrarily equivalent mixed-integer linear program. The MISDPs allow us to design an effective branch-and-cut algorithm with closed-form cuts that do not need to solve dual problems. For the proposed mixed-integer formulations, we further derive the theoretical optimality gaps of their continuous relaxations. Besides, we apply the greedy and local search algorithms to solving SPCA and derive their first-known approximation ratios. Our numerical experiments reveal that the exact methods we developed can efficiently find optimal solutions for data sets containing hundreds of features. Furthermore, our approximation algorithms demonstrate both scalability and near-optimal performance when benchmarked on larger data sets, specifically those with thousands of features. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research was supported in part by the Division of Civil, Mechanical and Manufacturing Innovation [Grant 224614], the Division of Computing and Communication Foundations [Grant 2246417], and the Office of Naval Research [Grant N00014-24-1-2066]. 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.2022.0372 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0372 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . 

We present a novel approach aimed at enhancing the efficacy of solving both regular and distributionally robust chance constrained programs using an empirical reference distribution. In general, these programs can be reformulated as mixed-integer programs (MIPs) by introducing binary variables for each scenario, indicating whether a scenario should be satisfied. Whereas existing methods have focused predominantly on either inner or outer approximations, this paper bridges this gap by studying a scheme that effectively combines these approximations via variable fixing. By checking the restricted outer approximations and comparing them with the inner approximations, we derive optimality cuts that can notably reduce the number of binary variables by effectively setting them to either one or zero. We conduct a theoretical analysis of variable fixing techniques, deriving an asymptotic closed-form expression. This expression quantifies the proportion of binary variables that should be optimally fixed to zero. Our empirical results showcase the advantages of our approach in terms of both computational efficiency and solution quality. Notably, we solve all the tested instances from literature to optimality, signifying the robustness and effectiveness of our proposed approach. History: Accepted by Andrea Lodi/Design & Analysis of Algorithms — Discrete. Funding: This work was supported by Office of Naval Research [N00014-24-1-2066]; Division of Civil, Mechanical and Manufacturing Innovation [2246414]. 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.0299 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0299 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .