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/ .

The soaring drug overdose crisis in the United States has claimed more than half a million lives in the past decade and remains a major public health threat. The ability to predict drug overdose deaths at the county level can help local communities develop action plans in response to emerging changes. Applying off-the-shelf machine learning algorithms for prediction can be challenging due to the heterogeneous risk profiles of the counties and suppressed data in common publicly available data sources. To fill these gaps, we develop a cluster-aware supervised learning (CASL) framework to enhance the prediction of county-level drug overdose deaths. This CASL model simultaneously clusters counties into groups based on geographical and socioeconomic characteristics and minimizes the loss function that accounts for suppressed values and cluster-specific regularization. Our computational study uses real-world data from 2010 to 2021, focusing on the ten states most severely impacted by the drug overdose crisis. The results demonstrate that our proposed CASL framework significantly outperforms state-of-the-art methods by achieving a superior balance in prediction accuracy for both unsuppressed and suppressed observations. The proposed model also identifies different clusters of counties, capturing heterogeneous patterns of overdose mortality among counties of diverse characteristics.

We study a federated classification problem over a network of multiple clients and a central server, in which each client’s local data remains private and is subject to uncertainty in both the features and labels. To address these uncertainties, we develop a novel Federated Distributionally Robust Support Vector Machine (FDR-SVM), robustifying the classification boundary against perturbations in local data distributions. Specifically, the data at each client is governed by a unique true distribution that is unknown. To handle this heterogeneity, we develop a novel Mixture of Wasserstein Balls (MoWB) ambiguity set, naturally extending the classical Wasserstein ball to the federated setting. We then establish theoretical guarantees for our proposed MoWB, deriving an out-of-sample performance bound and showing that its design preserves the separability of the FDR-SVM optimization problem. Next, we rigorously derive two algorithms that solve the FDR-SVM problem and analyze their convergence behavior as well as their worst-case time complexity. We evaluate our algorithms on industrial data and various UCI datasets, whereby we demonstrate that they frequently outperform existing state-of-the-art approaches.

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/ .

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/ .

MU-MIMO beamforming is a key technology for 5G networks, relying on Channel State Information (CSI). However, in practice, the estimated CSI in reality is prone to uncertainty. Further, a MU-MIMO beamforming solution must be derived within a millisecond to be useful for real-time 5G applications. We present ReDBeam—a real-time data-driven beamforming solution for MU-MIMO using limited CSI data samples. The main novelties of ReDBeam are a parallel algorithm and an optimized GPU implementation. ReDBeam delivers a MU-MIMO beamforming solution within 1 millisecond to meet the probabilistic data rate requirements from the users, and minimize a base station’s power consumption. Through extensive experiments, we show that ReDBeam consistently meets the stringent 1-millisecond real-time requirement and is orders of magnitude faster than other state-of-the-art algorithms. ReDBeam conclusively demonstrates that MU-MIMO beamforming with data rate requirements can be achieved in real-time using only limited CSI data samples.

The optimization of preventive maintenance (PM) intervals traditionally follows predict-then-optimize (PTO) frameworks. These involve two sequential steps: training a statistical model to estimate the failure time distribution (FTD) and then integrating it into an optimization model for deciding the optimal PM interval. However, PTO models may have poor out-of-sample performance if the fitted FTD differs significantly from the true distribution or fails to capture covariate effects. To overcome these issues, this paper introduces a contextual distributionally robust optimization (DRO) model for computing PM intervals. The proposed model integrates empirical failure time data directly into the optimization framework without assuming specific distributions. Our setting assumes that the component FTD is affected by covariates. Therefore, our formulation seeks to exploit covariate knowledge to compute efficient PM decisions conditional on the observed covariates. We formulate a DRO model that accounts for potential misspecifications of the empirical FTD. This DRO formulation aims to minimize the long-term maintenance cost rate by optimizing PM decision policies over an infinite space, where these policies map covariate information to optimal PM intervals. We demonstrate that the proposed DRO model admits tractable mixed-integer linear programming reformulations in various practical cases. The efficacy of our model is demonstrated through computational studies involving simulated and real-world failure time data.

We consider the problem of learning fair policies for multi-stage selection problems from observational data. This problem arises in several high-stakes domains such as company hiring, loan approval, or bail decisions where outcomes (e.g., career success, loan repayment, recidivism) are only observed for those selected. We propose a multi-stage framework that can be augmented with various fairness constraints, such as demographic parity or equal opportunity. This problem is a highly intractable infinite chance-constrained program involving the unknown joint distribution of covariates and outcomes. Motivated by the potential impact of selection decisions on people’s lives and livelihoods, we propose to focus on interpretable linear selection rules. Leveraging tools from causal inference and sample average approximation, we obtain an asymptotically consistent solution to this selection problem by solving a mixed binary conic optimization problem, which can be solved using standard off-the-shelf solvers. We conduct extensive computational experiments on a variety of datasets adapted from the UCI repository on which we show that our proposed approaches can achieve an 11.6% improvement in precision and a 38% reduction in the measure of unfairness compared to the existing selection policy.

MU-MIMO beamforming is a key technology for 5G/NextG networks. In practice, MU-MIMO beamforming requires Channel State Information (CSI) and is prone to uncertainty. Furthermore, a beamforming solution must be derived within a millisecond (ms) to be useful for real-time (RT) 5G applications. We present ReDBeam-a RT data-driven beamforming solution for MU-MIMO using limited CSI data samples. The main contribution of ReDBeam is a parallel algorithm and an optimized GPU implementation. ReDBeam minimizes the base station (BS)'s power consumption while offering a probabilistic guarantee of users' data rates. It is purposefully designed to take advantage of the vast parallel processing capability in commercial off-the-shelf GPUs. Through extensive experiments, we show that ReDBeam can meet the 1 ms RT requirement and is orders of magnitude faster than other state-of-the-art algorithms for the same problem.

The classical Canonical Correlation Analysis (CCA) identifies the correlations between two sets of multivariate variables based on their covariance, which has been widely applied in diverse fields such as computer vision, natural language processing, and speech analysis. Despite its popularity, CCA can encounter challenges in explaining correlations between two variable sets within high-dimensional data contexts. Thus, this paper studies Sparse Canonical Correlation Analysis (SCCA) that enhances the interpretability of CCA. We first show that SCCA generalizes three well-known sparse optimization problems, sparse PCA, sparse SVD, and sparse regression, which are all classified as NP-hard problems. This result motivates us to develop strong formulations and efficient algorithms. Our main contributions include (i) the introduction of a combinatorial formulation that captures the essence of SCCA and allows the development of exact and approximation algorithms; (ii) the establishment of the complexity results for two low-rank special cases of SCCA; and (iii) the derivation of an equivalent mixed-integer semidefinite programming model that facilitates a specialized branch-and-cut algorithm with analytical cuts. The effectiveness of our proposed formulations and algorithms is validated through numerical experiments.

We study the D-optimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NP-hard and has no constant-factor polynomial-time approximation algorithm unless P = NP. Therefore, to solve the DDF problem effectively, we propose two convex integer-programming formulations and investigate their corresponding complementary and Lagrangian-dual problems. Leveraging the concavity of the objective functions in the two proposed convex integer-programming formulations, we design an exact algorithm, aimed at solving the DDF problem to optimality. We further derive a family of submodular valid inequalities and optimality cuts, which can significantly enhance the algorithm performance. We also develop scalable randomized-sampling and local-search algorithms with provable performance guarantees. Finally, we test our algorithms using real-world data on the new phasor-measurement-units placement problem for modern power grids, considering the existing conventional sensors. Our numerical study demonstrates the efficiency of our exact algorithm and the scalability and high-quality outputs of our approximation algorithms. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: Y. Li and W. Xie were supported in part by Division of Civil, Mechanical and Manufacturing Innovation [Grant 2046414] and Division of Computing and Communication Foundations [Grant 2246417]. J. Lee was supported in part by Air Force Office of Scientific Research [Grants FA9550-19-1-0175 and FA9550-22-1-0172]. M. Fampa was supported in part by Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 305444/2019-0 and 434683/2018-3]. F. Qiu and R. Yao were supported in part by the U.S. Department of Energy Advanced Grid Modeling Program under [Grant DE-OE0000875]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.0235 .

Channel State Information (CSI) is a critical piece of information for MU-MIMO beamforming. However, CSI estimation errors are inevitable in practice. The random and uncertain nature of CSI estimation errors poses significant challenges to MU-MIMO beamforming. State-of-the-art works addressing such a CSI uncertainty can be categorized into model-based and data-driven works, both of which have limitations when providing a performance guarantee to the users. In contrast, this paper presents Limited Sample-based Beamforming (LSBF)—a novel approach to MU-MIMO beamforming that only uses a limited number of CSI data samples (without assuming any knowledge of channel distributions). Thanks to the use of CSI data samples, LSBF enjoys flexibility similar to data-driven approaches and can provide a theoretical guarantee to the users—a major strength of model-based approaches. To achieve both, LSBF employs chance-constrained programming (CCP) and utilizes the$\infty $-Wasserstein ambiguity set to bridge the unknown CSI distribution with limited CSI samples. Through problem decomposition and a novel bilevel formulation for each subproblem based on limited CSI data samples, LSBF solves each subproblem with a binary search and convex approximation. We show that LSBF significantly improves the network performance while providing a probabilistic data rate guarantee to the users.

Vehicles with adaptive cruise control, i.e., SAE Levels 1 and 2 automated vehicles (AVs), have been operating on roads with a significant and rapidly growing penetration rate. Identifying these AVs is critical to understanding near-future mixed traffic characteristics and managing highway mobility and safety. This study identifies adaptive cruise control-equipped vehicles from human-driven vehicles (HVs) by constructing a set of learning-based models using car-following trajectories in a short time window. It is extendible to Level 3 and + AV identification when data is available. To compare model performance and draw physical insights, two physics-based models are proposed based on the premise that, in general, the car-following behavior of an AV is less volatile than an HV. Four car-following datasets, including AV makes from different manufacturers, are mixed to build a comprehensive identification model. Results show that physics-based approaches identify more than 80% AVs and 70% HVs. The identification accuracy of learning-based models is even higher. For example, the cluster-aware long short-term memory network identifies 98.79% of AVs and 95.45% of HVs. Learning-based identification models developed by this study can be integrated with the existing infrastructure (e.g., surveillance cameras), which have been used to extract car-following trajectories, to detect AVs in mixed traffic streams. This opens unparalleled data-driven opportunities to analyze and control mixed traffic to enhance safety (e.g., notifying surrounding traffic of the presence of AVs) and mobility (e.g., opening AV dedicated lanes when the percentage is great enough).

Accurate estimation of Channel State Information (CSI) is essential to design MU-MIMO beamforming. However, errors in CSI estimation are inevitable in practice. State-of-the-art works model CSI as random variables and assume certain specific distributions or worst-case boundaries, both of which suffer performance issues when providing performance guarantees to the users. In contrast, this paper proposes a Data-Driven Beamforming (D2BF) that directly handles the available CSI data samples (without assuming any particular distributions). Specifically, we employ chance-constrained programming (CCP) to provide probabilistic data rate guarantees to the users and introduce ∞-Wasserstein ambiguity set to bridge the unknown CSI distribution with the available (limited) data samples. Through problem decomposition and a novel bilevel formulation for each subproblem, we show that each subproblem can be solved by binary search and convex approximation. We also validate that D2BF offers better performance than the state-of-the-art approach while meeting probabilistic data rate guarantees to the users.

This paper proposes a cluster-aware supervised learning (CluSL) framework, which integrates the clustering analysis with supervised learning. The objective of CluSL is to simultaneously find the best clusters of the data points and minimize the sum of loss functions within each cluster. This framework has many potential applications in healthcare, operations management, manufacturing, and so on. Because CluSL, in general, is nonconvex, we develop a regularized alternating minimization (RAM) algorithm to solve it, where at each iteration, we penalize the distance between the current clustering solution and the one from the previous iteration. By choosing a proper penalty function, we show that each iteration of the RAM algorithm can be computed efficiently. We further prove that the proposed RAM algorithm will always converge to a stationary point within a finite number of iterations. This is the first known convergence result in cluster-aware learning literature. Furthermore, we extend CluSL to the high-dimensional data sets, termed the F-CluSL framework. In F-CluSL, we cluster features and minimize loss function at the same time. Similarly, to solve F-CluSL, a variant of the RAM algorithm (i.e., F-RAM) is developed and proven to be convergent to an [Formula: see text]-stationary point. Our numerical studies demonstrate that the proposed CluSL and F-CluSL can outperform the existing ones such as random forests and support vector classification, both in the interpretability of learning results and in prediction accuracy. Summary of Contribution: Aligned with the mission and scope of the INFORMS Journal on Computing, this paper proposes a cluster-aware supervised learning (CluSL) framework, which integrates the clustering analysis with supervised learning. Because CluSL is, in general, nonconvex, a regularized alternating projection algorithm is developed to solve it and is proven to always find a stationary solution. We further generalize the framework to the high-dimensional data set, F-CluSL. Our numerical studies demonstrate that the proposed CluSL and F-CluSL can deliver more interpretable learning results and outperform the existing ones such as random forests and support vector classification in computational time and prediction accuracy.

Robust PCA (RPCA) and its tensor extension, namely, Robust Tensor PCA (RTPCA), provide an effective framework for background/foreground separation by decomposing the data into low-rank and sparse components, which contain the background and the foreground (moving objects), respectively. However, in real-world applications, the presence of missing pixels is a very common and challenging issue due to errors in the acquisition process or manufacturer defects. RPCA and RTPCA are not able to recover the background and foreground simultaneously with missing pixels. This study aims to address the problem of background/foreground separation with missing pixels by combining video recovery and background/foreground separation into a single framework. To achieve this goal, a smooth robust tensor completion (SRTC) model is proposed to recover the data and decompose it into the static background and smooth foreground, respectively. An efficient algorithm based on tensor proximal alternating minimization (tenPAM) is implemented to solve the proposed model with a global convergence guarantee under very mild conditions. Extensive experiments on actual data demonstrate that the proposed method significantly outperforms the state-of-the-art approaches for background/foreground separation with missing pixels.

This paper studies a multiproduct newsvendor problem with customer-driven demand substitution, where each product, once run out of stock, can be proportionally substituted by the others. This problem has been widely studied in the literature; however, because of nonconvexity and intractability, only limited analytical properties have been reported and no efficient approaches have been proposed. This paper first completely characterizes the optimal order policy when the demand is known and reformulates this nonconvex problem as a binary quadratic program. When the demand is random, we formulate the problem as a two-stage stochastic integer program, derive several necessary optimality conditions, prove the submodularity of the profit function, and also develop polynomial-time approximation algorithms and show their performance guarantees. We further propose a tight upper bound via nonanticipativity dual, which is proven to be very close to the optimal value and can yield a good-quality feasible solution under a mild condition. Our numerical investigation demonstrates effectiveness of the proposed algorithms. Moreover, several useful findings and managerial insights are revealed from a series of sensitivity analyses.

The recent increase in applications of high-dimensional data poses a severe challenge to data analytics, such as supervised classification, particularly for online applications. To tackle this challenge, efficient and effective methods for feature extraction are critical to the performance of classification analysis. The objective of this work is to develop a new supervised feature extraction method for high-dimensional data. It is achieved by developing a clustered discriminant regression (CDR) to extract informative and discriminant features for high-dimensional data. In CDR, the variables are clustered into different groups or subspaces, within which feature extraction is performed separately. The CDR algorithm, which is a greedy approach, is implemented to obtain the solution toward optimal feature extraction. One numerical study is performed to demonstrate the performance of the proposed method for variable selection. Three case studies using healthcare and additive manufacturing data sets are accomplished to demonstrate the classification performance of the proposed methods for real-world applications. The results clearly show that the proposed method is superior over the existing method for high-dimensional data feature extraction.Note to Practitioners—This article forwards a new supervised feature extraction method termed clustered discriminant regression. This method is highly effective for classification analysis of high-dimensional data, such as images or videos, where the number of variables is much larger than the number of samples. In our case studies on healthcare and additive manufacturing, the performance of classification analysis based on our method is superior over the existing feature extraction methods, which is confirmed by using various popular classification algorithms. For image classification, our method with elaborately selected classification algorithms can outperform a convolutional neural network. In addition, the computation efficiency of the proposed method is also promising, which enables its online applications, such as advanced manufacturing process monitoring and control.

In an optimal design problem, we are given a set of linear experiments $v_1,…,v_n\in \mathbb{R}^d$ and $k \geq d$, and our goal is to select a set or a multiset $S \subseteq [n]$ of size $k$ such that $\Phi((\sum_{i \in S} v_i v_i^\top )^{-1})$ is minimized. When $\Phi(M) = Determinant(M)^{1/d}$, the problem is known as the D-optimal design problem, and when $\Phi(M) = Trace(M)$, it is known as the A-optimal design problem. One of the most common heuristics used in practice to solve these problems is the local search heuristic, also known as the Fedorov’s exchange method (Fedorov, 1972). This is due to its simplicity and its empirical performance (Cook and Nachtrheim, 1980; Miller and Nguyen, 1994; Atkinson et al., 2007). However, despite its wide usage no theoretical bound has been proven for this algorithm. In this paper, we bridge this gap and prove approximation guarantees for the local search algorithms for D-optimal design and A-optimal design problems. We show that the local search algorithms are asymptotically optimal when $\frac{k}{d}$ is large. In addition to this, we also prove similar approximation guarantees for the greedy algorithms for D-optimal design and A-optimal design problems when $\frac{k}{d}$ is large.

Experimental design is a classical area in statistics [21] and has also found new applications in machine learning[2]. In the combinatorial experimental design problem, the aim is to estimate an unknown m-dimensional vector x from linear measurements where a Gaussian noise is introduced in each measurement. The goal is to pick k out of the given n experiments so as to make the most accurate estimate of the unknown parameter x. Given a set S of chosen experiments, the most likelihood estimate x′ can be obtained by a least squares computation. One of the robust measures of error estimation is the D-optimality criterion [27] which aims to minimize the generalized variance of the estimator. This corresponds to minimizing the volume of the standard confidence ellipsoid for the estimation error x – x′. The problem gives rise to two natural variants depending on whether repetitions of experiments is allowed or not. The latter variant, while being more general, has also found applications in geographical location of sensors [19]. We show a close connection between approximation algorithms for the D-optimal design problem and constructions of approximately m-wise positively correlated distributions. This connection allows us to obtain a approximation for the D-optimal design problem with and without repetitions giving the first constant factor approximation for the problem. We then consider the case when the number of experiments chosen is much larger than the dimension m and show one can obtain (1 – ∊)-approximation if when repetitions are allowed and if when no repetitions are allowed improving on previous work.