INFORMS 2021 Program Book

INFORMS Anaheim 2021

WE28

5 - 3-D Geo-graphs: Efficient Contiguity Verification for 3-D Graph Partitioning Ian G. Ludden, PhD Student, University of Illinois at Urbana- Champaign, Urbana, IL, United States, Douglas M. King, Sheldon H. Jacobson The constrained contiguous graph partitioning problem (CCGP) requires partitioning the vertices of a node-weighted graph into connected parts with balanced weights to minimize a cost function. CCGP is often solved by local search metaheuristics with a flip operation, which transfers a vertex between parts if the transfer preserves contiguity. For planar graphs, previous work proposes the geo-graph data structure for efficiently verifying contiguity after flips. This work extends the geo-graph to three-dimensional graphs such as 3-D Voronoi diagrams and tetrahedral/hexahedral meshes. WE26 CC Room 206A In Person: Bridging Discrete and Continuous Optimization General Session Chair: Hassan Mortagy, Georgia Institute of Technology, Atlanta, GA, 30308-1007, United States 1 - Revisiting Priority K-center: Fairness and Outliers Maryam Negahbani, Dartmouth College, Hanover, NH, United States, Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri Clustering is a well-studied unsupervised learning and facility location problem. In this talk we focus on the k-center objective: Given a set of points in the metric space and a parameter k, cover the points using k balls with minimum radius. We discuss two definitions of fair k-center, individual fairness (introduced by Jung et al. FORC ‘20) and the lottery model (introduced by Harris et. al. NeurIPS ‘18) and show how they are connected to a previously studied problem called the priority k-center problem (Plesnik ‘87). Our main contribution is approximating priority k-center with outliers and providing a framework for approximation the problem with general constraints on the set of solution centers. 2 - Electrical Flows Over Spanning Trees ““Ix” “Hassan Mortagy, Georgia Institute of Technology, Atlanta, GA, 30308-1007, United States, Swati Gupta, Ali Khodabakhsh, Evdokia Velinova Nikolova The network reconfiguration problem seeks to find a rooted tree T such that the energy of the (unique) feasible electrical flow over T is minimized. The tree requirement on the support of the flow is motivated by operational constraints in electricity distribution networks. We give the first provable approximation guarantees for this problem. We provide novel lower bounds and corresponding approximation factors for various settings ranging from min{O(m − n), O(n)} to O(1) for grids with uniform edge resistances and demands. To obtain the result for general graphs, we propose a new spectral graph sparsification approach, which may be of independent interest. Using insights from our theoretical results, we propose a general heuristic that is orders of magnitude faster than existing methods in the literature, while obtaining comparable performance. WE27 CC Room 206B In Person: Stochastic Optimization in Machine Learning General Session Chair: Zhe Zhang, Georgia Tech, Georgia Tech, Atlanta, GA, 30318, United States 1 - Higher-order Optimistic Methods for Saddle Point Problems Aryan Mokhtari, University of Texas at Austin, Austin, TX, 78750- 3312, United States In this talk, we consider solving saddle point problems, and, in particular, we discuss the concept of “optimism” or “negative momentum” a technique which is observed to have superior empirical performance in training GANs. The goal of this talk is to provide a theoretical understanding on why optimism helps, in particular why the Optimistic Gradient Descent Ascent (OGDA) algorithm performs well in practice. To do so, we first consider the classical Proximal Point algorithm which is an implicit algorithm to solve this problem. We then show that OGDA inherently tries to approximate the proximal point method, and this is the rationale behind the “negative momentum” term in the update of OGDA. We also extend our theoretical results to the case of higher-order methods. In particular, we present higher-order optimistic methods that exploit higher-order information of the function to find a saddle point faster than first-order methods.

2 - A Progressive Barrier for Constrained Derivative-Free Multiobjective Optimization Ludovic Salomon, Polytechnique Montreal, Montréal, QC, Canada, Sebastien Le Digabel, Jean Bigeon The last decade has seen the development of new efficient convergent-based derivative-free and blackbox optimization algorithms for multiobjective optimization, most of them extensions of reliable single-objective methods. However, very few have been designed to take into account inequality blackbox constraints. This work presents an extension of the single-objective blackbox Mesh Adaptive Direct Search (MADS) algorithm with the progressive barrier to multiobjective blackbox optimization. It integrates the knowledge of inequality constraints. Numerical experiments on synthetic benchmarks and engineering applications show that this new method is competitive according to other state- of-the-art algorithms. 3 - Optimal Distributed Algorithms for Risk Neutral and Robust Optimization Zhe Zhang, ISyE, Gatech, Atlanta, GA, 30332, United States, Guanghui Lan We study the distributed optimization of risk averse functions of the form $\max_{p \in \mathcal{P}}\sum_{i=1}^{m} p_i f_i(x)$ over a network, where $\mathcal{P}$ denotes the probability ambiguity set and convex cost functions $f_i$ are local to their respect agents in the network. The problem generalizes the well-studied finite-sum distributed optimization problem and poses new challenges due to the varying $p$ in $\mathcal{P}.$ Its importance stems from the need to avoid risk or to handle unknown underlying probability distribution over agents. In this paper, we consider both centralized and decentralized settings with either smooth or nonsmooth $f_i$s. We develop minimax models to illustrate theoretically possible lower communication complexity bounds and propose primal algorithms to achieve almost tight communication complexities. WE28 - Cancelled CC Room 207B In Person: Recent Developments on Statistical Process Control General Session Chair: Kai Yang, University of Florida, Gainesville, FL, 32610-3010, United States 1 - Water Resource Surveillance for the Salton Sea in California by Adaptive Sequential Monitoring of its Landsat Images Fan Yi, University of Florida, Gainesville, FL, United States Gradual loss of water resource in the Salton Sea has got much attention from researchers recently for its damage to the local environment and ecosystems. To monitor the water resource of the lake, researchers usually obtain certain water resource indices manually from databases such as the satellite images of the region. We develop a new method to monitor the area of the Salton Sea automatically. By this method, the lake is first segmented properly from each satellite image by an image segmentation procedure, and then its area is computed by a numerical algorithm. The sequence of lake areas computed from satellite images taken at different time points is then monitored by a new adaptive CUSUM chart. Numerical studies show that the proposed method works well for the water resource surveillance application. 2 - Transparent Sequential Learning for Statistical Process Control Xiulin Xie, University of Florida, Gainesville, FL, United States, Peihua Qiu Machine learning methods have been widely used in different applications, including SPC. For handling SPC problems, conventional machine learning methods would have some difficulties. In this project, we extend the self-starting process monitoring idea that has been employed widely in modern SPC research to a general learning framework for process control and monitoring. Under the new framework, process characteristics to learn are well specified in advance, and process learning is sequential in the sense that the learned process characteristics keep being updated during process monitoring. The learned process characteristics are then incorporated into a control chart for detecting process distributional shift based on all available data by the current observation time. Numerical studies show that the new learning framework is reliable and effective

177