More Like this

1. Efficient Nested Simulation Experiment Design via the Likelihood Ratio Method

   https://doi.org/10.1287/ijoc.2022.0392  

   Feng, Ben Mingbin; Song, Eunhye (June 2024, INFORMS Journal on Computing)

   In the nested simulation literature, a common assumption is that the experimenter can choose the number of outer scenarios to sample. This paper considers the case when the experimenter is given a fixed set of outer scenarios from an external entity. We propose a nested simulation experiment design that pools inner replications from one scenario to estimate another scenario’s conditional mean via the likelihood ratio method. Given the outer scenarios, we decide how many inner replications to run at each outer scenario as well as how to pool the inner replications by solving a bilevel optimization problem that minimizes the total simulation effort. We provide asymptotic analyses on the convergence rates of the performance measure estimators computed from the optimized experiment design. Under some assumptions, the optimized design achieves [Formula: see text] mean squared error of the estimators given simulation budget [Formula: see text]. Numerical experiments demonstrate that our design outperforms a state-of-the-art design that pools replications via regression. History: Accepted by Bruno Tuffin, Area Editor for Simulation. Funding: This work was supported by the National Science Foundation [Grant CMMI-2045400] and the Natural Sciences and Engineering Research Council of Canada [Grant RGPIN-2018-03755]. 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.0392 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0392 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . 

   more » « less
2. Exact and Approximation Algorithms for Sparse Principal Component Analysis

   https://doi.org/10.1287/ijoc.2022.0372  

   Li, Yongchun; Xie, Weijun (July 2024, INFORMS Journal on Computing)

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

   more » « less
3. Asymptotically Tight MILP Approximations for a Nonconvex QCP

   https://doi.org/10.1287/ijoc.2024.0719  

   Jiang, Shiyi; Cheng, Jianqiang; Pan, Kai; Yang, Boshi (May 2025, INFORMS Journal on Computing)

   Nonconvex quadratically constrained programs (QCPs) are generally NP-hard and challenging problems. In this paper, we propose two novel mixed-integer linear programming (MILP) approximations for a nonconvex QCP. Our method begins by utilizing an eigenvalue-based decomposition to express the nonconvex quadratic function as the difference of two convex functions. We then introduce an additional variable to partition each nonconvex constraint into a second-order cone (SOC) constraint and the complement of an SOC constraint. We employ two polyhedral approximation approaches to approximate the SOC constraint. The complement of an SOC constraint is approximated using a combination of linear and complementarity constraints. As a result, we approximate the nonconvex QCP with two linear programs with complementarity constraints (LPCCs). More importantly, we prove that the optimal values of the LPCCs asymptotically converge to that of the original nonconvex QCP. By proving the boundedness of the LPCCs, we further reformulate the LPCCs as MILPs. We demonstrate the effectiveness of our approaches via numerical experiments by applying our proposed approximations to randomly generated instances and two application problems: the joint decision and estimation problem and the two-trust-region subproblem. The numerical results show significant advantages of our approaches in terms of solution quality and computational time compared with existing benchmark approaches. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods and Analysis. Funding: K. Pan was supported in part by the Research Grants Council of Hong Kong [Grant 15503723]. J. Cheng and B. Yang were supported in part by the Office of Naval Research [Grant N00014-20-1-2154]. J. Cheng was supported in part by the National Science Foundation [Grant ECCS-2404412]. B. Yang was supported in part by the Air Force Office of Scientific Research [Grant FA9550-23-1-0508]. 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.0719 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0719 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . 

   more » « less
4. Maximizing Engagement in Large-Scale Social Networks

   https://doi.org/10.1287/ijoo.2022.0024  

   Kroger, Samuel; Validi, Hamidreza; Hicks, Illya V (July 2024, INFORMS Journal on Optimization)

   Motivated by the importance of user engagement as a crucial element in cascading leaving of users from a social network, we study identifying a largest relaxed variant of a degree-based cohesive subgraph: the maximum anchored k-core problem. Given graph [Formula: see text] and integers k and b, the maximum anchored k-core problem seeks to find a largest subset of vertices [Formula: see text] that induces a subgraph with at least [Formula: see text] vertices of degree at least k. We introduce a new integer programming (IP) formulation for the maximum anchored k-core problem and conduct a polyhedral study on the polytope of the problem. We show the linear programming relaxation of the proposed IP model is at least as strong as that of a naïve formulation. We also identify facet-defining inequalities of the IP formulation. Furthermore, we develop inequalities and fixing procedures to improve the computational performance of our IP model. We use benchmark instances to compare the computational performance of the IP model with (i) the naïve IP formulation and (ii) two existing heuristic algorithms. Our proposed IP model can optimally solve half of the benchmark instances that cannot be solved to optimality either by the naïve model or the existing heuristic approaches. Funding: This work is funded by the National Science Foundation (NSF) [Grant DMS-2318790] titled AMPS: Novel Combinatorial Optimization Techniques for Smartgrids and Power Networks. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2022.0024 . 

   more » « less
5. On the Value of Risk-Averse Multistage Stochastic Programming in Capacity Planning

   https://doi.org/10.1287/ijoc.2023.0396  

   Yu, Xian; Shen, Siqian (October 2024, INFORMS Journal on Computing)

   We consider a risk-averse stochastic capacity planning problem under uncertain demand in each period. Using a scenario tree representation of the uncertainty, we formulate a multistage stochastic integer program to adjust the capacity expansion plan dynamically as more information on the uncertainty is revealed. Specifically, in each stage, a decision maker optimizes capacity acquisition and resource allocation to minimize certain risk measures of maintenance and operational cost. We compare it with a two-stage approach that determines the capacity acquisition for all the periods up front. Using expected conditional risk measures, we derive a tight lower bound and an upper bound for the gaps between the optimal objective values of risk-averse multistage models and their two-stage counterparts. Based on these derived bounds, we present general guidelines on when to solve risk-averse two-stage or multistage models. Furthermore, we propose approximation algorithms to solve the two models more efficiently, which are asymptotically optimal under an expanding market assumption. We conduct numerical studies using randomly generated and real-world instances with diverse sizes, to demonstrate the tightness of the analytical bounds and efficacy of the approximation algorithms. We find that the gaps between risk-averse multistage and two-stage models increase as the variability of the uncertain parameters increases and decrease as the decision maker becomes more risk averse. Moreover, a stagewise-dependent scenario tree attains much higher gaps than a stagewise-independent counterpart, whereas the latter produces tighter analytical bounds. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work of Dr. X. Yu was partially supported by the U.S. National Science Foundation Division of Information and Intelligent Systems [Grant 2331782]. 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.0396 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0396 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . 

   more » « less