INFORMS 2021 Program Book

INFORMS Anaheim 2021

WB14

WB12 CC Room 304D In Person: Bilevel Optimization/Bayesian

WB13 CC Room 201A In Person: Modeling and Optimization for Decision Analytics General Session Chair: Yasaman Ghasemi, The University of Texas at Arlington, Arlington, TX, United States 1 - Heatwave Prediction using Classification and Regression Trees Gazi Md Daud Iqbal, Coppin State University, Baltimore, MD, United States, Jay Michael Rosenberger, Lidan Ha, Sadie Gregory Global temperature is increasing at an alarming rate, which increases the number of heatwaves. Many people die as a direct or indirect consequence of a heatwave, and elderly people are most affected by a heatwave. Predicting the occurrence of a heatwave can save lives. Because of its geographical location, Bangladesh is one country that is particularly vulnerable to heatwaves. The Bangladesh Meteorological Department collects temperature data at ten weather stations. Data shows that a majority of heatwaves occur in summer months, namely, April, May, and June. In this research, we develop Classification and Regression Tree (CART) models to predict the likelihood of a heatwave in the next 7 days and 28 days using previous two weeks daily temperature. 2 - Modeling Patrol Operations using Agent-Based Simulation Yasaman Ghasemi, The University of Texas at Arlington, Arlington, TX, United States, Yuan Zhou, Victoria C. Chen, Kent Ryan Kerley The complex nature of the policing system often makes it very challenging to manage and control. The dynamic and stochastic criminal behavior, compounded with limited policing resources, are rendered current police operations ineffective and inefficient. In this study, a computer simulation-optimization framework is developed to conquer these weaknesses by addressing the dynamically changing complexities and uncertainties in police operations and adaptively optimizing operational performance based on the state of the policing system. A real-world case study will be presented to illustrate how this framework is used in dynamic patrol deployment planning. WB14 CC Room 201B In Person: The Interplay Between Optimization and Statistics General Session Chair: Lijun Ding, Cornell University, Ithaca, NY, 14850-2842, United States 1 - Clustering Gaussian Mixtures with Unknown Covariances Kaizheng Wang, Columbia University, New York, NY, United States We investigate the clustering problem with data from a mixture of Gaussians that share a common but unknown covariance matrix. When there are only two equally-sized components, we derive a max-cut integer program for clustering based on maximum likelihood estimation. It is shown to achieve the statistical optimality in terms of the misclassification error. We also develop an efficient algorithm that returns optimal clustering but has worse sample complexity. We provide numerical verifications of the gap together with some theoretical evidence of a possible statistical-computational tradeoff. Finally, we propose and analyze a k-means program on transformed data to handle multiple components with possibly unequal weights. It is an extension of the max-cut program for the two-component case and enjoys similar optimality guarantees. 2 - Importance Sketching for Fast Low-rank Matrix/tensor Learning: Algorithm and High-order Convergence Anru Zhang, Duke University, Durham, NC, 53562, United States We consider the matrix/tensor rank constrained least-squares optimization. This problem covers many specific examples arising from applications, including matrix/tensor regression, completion, PCA/SVD, and phase retrieval. We propose a new algorithm RISRO based on a new sketching framework, recursive importance sketching. Several existing algorithms can be reinterpreted under the new sketching framework and RISRO offers clear advantages over them. RISRO is easy to implement and computationally efficient, where the core procedure in each iteration is only solving a dimension reduced least-squares. We establish a local quadratic rate of convergence for RISRO under mild conditions. We also discover a deep connection of RISRO to Riemannian manifold optimization. The effectiveness of RISRO is demonstrated in applications in machine learning and statistics.

Optimization General Session Chair: Raul Astudillo, Cornell University, Ithaca, NY, 14853-3801, United States 1 - Integer Programming Methods for Solving Binary Interdiction Games Ningji Wei, Heinz College, Carnegie Mellon University, Pittsburgh, PA, 19104, United States, Jose L. Walteros We study a general class of interdiction problems in which the solution space of both the leader and follower are characterized by two discrete sets: the leader’s strategy set and the follower’s structure set. The interaction between any strategy- structure pair is assumed to be binary, such that the strategy selected by the leader either interacts or not with the follower’s structure and if it does, the structure becomes unavailable. Many interdiction games fall into this type, including shortest paths, minimum spanning trees, minimum dominating sets interdiction, among others. We study a formulation for solving this general problem and analyze the properties of its convex hull. We develop a wide class of inequalities that generalizes several others that have appeared in the literature. We also study their facet-defining conditions and discuss the separation methods. 2 - Interdicting Low-diameter Cohesive Subgroups in Large-scale Social Networks Niloufar Daemi, Oklahoma State University, Stillwater, OK, United States, Juan Sebastian Borrero, Balabhaskar Balasundaram An s-club is a subset of vertices in graph G that induces a subgraph of diameter at most s. This concept was introduced in social network analysis to model the cohesive social subgroups as low-diameter clusters in a social network. Several recent articles in the literature address the detection of the largest cardinality s- club in a graph. In this article, we work on the s-club interdiction problem which diminishes the size of the largest s-club in a graph. We propose an interdiction model with an interdiction penalty instead of a hard budget constraint and design a decomposition algorithm to solve the problem. We test the effectiveness of our algorithm on two test-beds of benchmark instances. 3 - Sequential Network Interdiction with Learning under Asymmetric Information and Inexact Evader Jing Yang, University of Pittsburgh, Pittsburgh, PA, 15232, United States, Oleg A. Prokopyev, Denis R. Saure We consider a sequential network interdiction setting over a finite horizon, where in each period an interdictor with incomplete knowledge of the arc costs blocks at most k arcs, and an evader with complete knowledge about the costs traverses a path between two fixed nodes in the interdicted network. In each period, the interdictor’s objective function depends on a path taken by the evader after interdiction. We assume that in each period the interdictor observes the full path used by the evader. This information feedback is then used by the interdictor to refine his/her interdiction decisions in the subsequent time periods. In this talk, we analyze the implications of relaxing the standard assumption in the related literature that the evader’s response must be the shortest path in the interdicted network. 4 - Grey-Box Bayesian Optimization of Nested Functions Raul Astudillo, Cornell University, Operations Research And Information Engineer, Ithaca, NY, 14853-3801, United States, Peter Frazier We consider Bayesian optimization of objective functions that are the composition of multiple expensive-to-evaluate functions. While the standard Bayesian optimization approach observes only the objective value, our approach delivers greater sample efficiency by observing information that the standard approach ignores: the output of intermediate functions. Our approach models these functions using independent Gaussian processes and chooses the points to evaluate using as its acquisition function the expected improvement computed with respect to the implied posterior on the objective function. Although this acquisition function cannot be computed in closed form, we maximize it using a sample average approximation approach. Numerical experiments show that our approach substantially outperforms standard Bayesian optimization benchmarks.

151