Caihua Chen

Semidefinite programming (SDP) provides a powerful framework in applied mathematics with applications spanning optimization, machine learning, quantum computing, and beyond. However, the computational cost of solving large-scale SDP problems remains a significant practical limitation. We break this long-standing computational bottleneck through a synergistic codesign of low-rank algorithms and graphics processing unit (GPU) architectures, developing accelerated first-order methods that leverage both algorithmic innovations and hardware-aware implementation to achieve up to 4 orders of magnitude improvements in speed and scalability for large-scale SDPs with sparse and low-rank structure, thereby opening frontiers in large-scale scientific computing. Our solver, GPU-accelerated Low-Rank Alternating Direction Method of Multipliers Splitting (cuLoRADS), exemplifies this approach, combining the Burer-Monteiro method with a splitting scheme to efficiently solve massive-scale SDPs. Specifically, it can solve a set of MaxCut problems whose matrix variables have dimensions of 10 7 × 10 7 in 10 s to 1 min each on an NVIDIA H100 GPU with 80 GB of memory, whereas previously reported central processing unit solvers required dozens of hours. Additionally, cuLoRADS shows exceptional scalability by solving 1) a MaxCut problem with a 170 million × 170 million matrix variable and 2) a Minimum-Rank Matrix Completion problem with a 20 million × 20 million matrix variable and approximately 200 million constraints, both in a matter of minutes. It also resolves a long-standing SDP computational barrier in the quantum ordered search problem, which had remained unsolved for 18 y.

We study a joint wind farm planning and operational scheduling problem under decision-dependent uncertainty. Geographic heterogeneity in wind power resources induces stochastic fluctuations that can partially offset one another—a phenomenon known as the smoothing effect. Capturing this effect requires strategic capacity allocation, which introduces decision-dependent uncertainty. At the same time, joint planning and operations must address long-term complexity, where traditional stochastic optimization faces a trade-off between statistical robustness and computational burden. To address these challenges, we propose a two-stage distributionally robust optimization model with a decision-dependent Wasserstein ambiguity set, where both the distribution and the radius adapt to planning decisions. The resulting decision-dependent radius contracts at the O ( N − 1 / 2 ) rate and avoids the dimensionality dependence. The model is reformulated as a mixed-integer second-order cone programming, incorporating an empirical approximation and a regularization term that includes variance-covariance estimates for the wind power resource of each farm. We further establish finite-sample guarantees on both cost and power stability under the theoretically calibrated radius. These theoretical insights motivate an asymmetric sampling strategy that leverages large datasets for variance-covariance estimation while using smaller datasets for optimization. To improve computational efficiency, we develop a constraint generation based solution framework that accelerates the solution procedure by hundreds of times. Numerical experiments using different datasets validate the effectiveness of the solution framework and demonstrate the superior performance of the proposed model in risk management. Our results offer clear managerial implications for renewable energy planning under uncertainty: (i) information quality outweighs quantity—covariance information should be incorporated only when it is sufficiently reliable; otherwise, it may compromise power stability; and (ii) effective data utilization is more valuable than simply increasing data quantity—the asymmetric sampling strategy can achieve comparable performance with substantially lower computational effort.

In this research, we focus on improving service-oriented routing by addressing the nuanced challenge of punctuality through the consideration of couriers’ ability to ensure on-time deliveries. We utilize a comprehensive real-world data set from a cold chain logistics firm for analysis. Our empirical investigation indicates that relying solely on travel distance is inadequate for accurate delivery time prediction. We highlight critical elements, including couriers’ fixed effects and workload, as key covariates to improve prediction performance. Distinguishing our work from existing literature, we integrate couriers’ workload and location familiarity into our service-oriented routing model to enhance predictions of delivery times. We introduce the courier-assigned location mismatch (CALM) metric as a less intrusive approach to incorporating couriers’ location familiarity into their delivery efficiency. We propose the novel service-oriented considerate routing (SOCR) model; by minimizing the CALM metric, couriers are assigned routes within familiar territories to the extent possible within the total routing distance constraint. The considerate routing strategies could potentially reduce the stress couriers face when delivering in unfamiliar areas. Additionally, we develop the connection of the SOCR model with a robust satisficing approach. This strategy guarantees timely deliveries by effectively mitigating the effects of predictive inaccuracies and potential model misspecifications. To solve the SOCR model, we apply Benders decomposition for an exact solution and tabu search for a heuristic approach, demonstrating their effectiveness and superior out-of-sample performance. Notably, our heuristic solutions significantly outperform exact solutions of classical vehicle routing problems with deadlines, resulting in substantial improvements in timely delivery performance. This paper was accepted by Wolfram Wiesemann, data science. Funding: Y. Zhao and M. Sim were partially supported by the Ministry of Education, Singapore, under its 2019 Academic Research Fund Tier 3 [Grant MOE-2019-T3-1-010]. Z. Luo was supported by the National Natural Science Foundation of China [Grants 72222011, 72171112, and 72442006]. C. Chen was supported in part by the National Natural Science Foundation of China [Grants 72394363, 12431011, and 72394364]. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2024.05530 .

1. Inventory management is the core link of modern enterprise operation management (OM) and the main means for enterprises to coordinate supply and demand. With the development of economic globalis...

Multiagent reinforcement learning (MARL) has been widely investigated, ranging from theoretical analysis to real-life applications. However, the utilization of existing non-transparent neural network architectures has resulted in opaque decision-making processes, making it difficult for humans to understand and trust the models being used. Fundamentally, all data is a topological structure, which provides reliable transparency for MARL tasks due to its powerful relational expression capability, scalability, and explicit structural relationships. In this article, we propose a novel approach of graph cooperation modeling (GCM), explicitly capturing and comprehending the complex dynamics of collaborative relationships among agents with the graph structure. GCM learns a metric function to discern beneficial interactions among agents, integrating it into the agent aggregation strategy of a graph neural network (GNN) capable of modeling arbitrary-order interactions. Furthermore, GCM utilizes identity semantics together with global state and individual value functions to estimate the credit of each agent, enhancing each agent’s distinct focus on task-related regions. Extensive experiments on a range of challenging MARL benchmarks demonstrate that GCM not only delivers up to 28.75% relative performance gains on super-hard maps but also offers clear interpretability that provides insights into the underlying cooperative patterns.

This paper investigates efficient algorithm for Markov Decision Processes (MDPs) through Linear programming (LP). Generally, solving large-scale MDPs via standard LP solvers faces significant computational bottlenecks in matrix factorization. To tackle this problem, we introduced a novel sparse formulation for discounted MDPs using nonconvex regularization. Despite being combinatorial in nature, we show that the formulation can be solved efficiently by an alternating direction method of multipliers with linear convergence rate and a state-of-the-art performance.

We introduce a new first order method for solving the semidefinite programming (SDP) problem with a convex and differentiable objective based on the alternating direction method of multipliers (ADMM) and a matrix-splitting technique. Our algorithm has an advantage over the Burer–Monteiro (BM) approach as it involves much easier quadratically regularized subproblems in each iteration. For a linear objective, the subproblems are well-conditioned quadratic programs that can be efficiently solved by the standard conjugate gradient method. We show that our algorithm achieves sublinear or linear convergence rates to the Karush–Kuhn–Tucker solutions under different conditions. Based on this theoretical development, we present LoRADS, a new solver for linear SDP based on the low-rank ADMM splitting approach. LoRADS applies several strategies to significantly improve its efficiency. First, it initiates with a warm-start phase that uses the BM approach. Moreover, motivated by the advances on the SDP low-rank theory, LoRADS chooses an initial rank of logarithmic order and employs a dynamic approach to increase the rank. Although LoRADS does not necessarily ensure global optimality, it performs well on many important and large-scale problems, such as MaxCut and matrix completion. Notably, LoRADS solved (i) a MaxCut problem with the dimension of 1,048,576 in less than seven minutes and (ii) a matrix completion problem with 71,681,424 constraints and a 180,000 × 180,000 matrix in about half an hour, achieving accuracies below 1e-5 for both problems. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: C. Li, Z. Lin, and D. Ge were supported in part by the National Natural Science Foundation of China [Grants 72225009, 72394360, and 72394365]. C. Chen was supported in part by the National Natural Science Foundation of China [Grants 72394363/72394360, 12431011 and 12122107] and the Fundamental Research Funds for the Central Universities. Q. Deng was supported in part by the National Natural Science Foundation of China [Grants 72394364/72394360 and 12571325] and the Natural Science Foundation of Shanghai [Grant 24ZR1421300]. H. Liu was supported in part by the Young Elite Scientists Sponsorship Program [Grant CAST 2023QNRC001] and the National Natural Science Foundation of China [Grants NSFC-72192830 and 72192832]. 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.0701 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0701 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

LoRADS is an enhanced first-order method solver for low rank Semi-definite programming problems (SDPs). LoRADS is written in ANSI C and is maintained by Cardinal Operations COPT development team. More features are still under active development.

We develop an adaptive Nesterov accelerated proximal gradient (adaNAPG) algorithm for stochastic composite optimization problems, boosting the Nesterov accelerated proximal gradient (NAPG) algorithm through the integration of an adaptive sampling strategy for gradient estimation. We provide a complexity analysis demonstrating that the new algorithm, adaNAPG, achieves both the optimal iteration complexity and the optimal sample complexity as outlined in the existing literature. Additionally, we establish a central limit theorem for the iteration sequence of the new algorithm adaNAPG, elucidating its convergence rate and efficiency.