INFORMS 2021 Program Book

INFORMS Anaheim 2021

WE08

algorithm is “local” if the decision at each node is based on information only about a constant radius neighborhood of the node. We construct a local algorithm for this dynamic decision problem and show that our algorithm is near-optimal when edge rewards are small with respect to the randomness in node rewards and the graph degree. WE12 CC Room 304D In Person: Political Redistricting Part I of II General Session Chair: Hamidreza Validi, Rice University, Stillwater, OK, 74078, United States 1 - An Analysis of Multilevel Algorithms for Compact Districting Rahul Swamy, University of Illinois at Urbana-Champaign, Urbana, IL, 61801, United States, Douglas M. King, Sheldon H Jacobson The Compact Districting Problem (CDP) divides a region into districts (subregions) such that each district is compact, balanced in population, and contiguous. This is a fundamental problem that arises in many applications ranging from political redistricting to service territory design. A multilevel algorithm is a popular algorithm in graph partitioning that has been adapted to solve CDPs in recent work. This talk provides an analysis of the performance of the multilevel algorithm for CDPs. The goal is to compare its performance for various parameter settings to benefit a decision-maker that seeks to find scalable solutions to a CDP. 2 - Compactness in Redistricting; Red Flag or Red Herring? Laurel Travis, Virginia Tech, Blacksburg, VA, 24060-8700, United States, Jamie Fravel, Nicholas Goedert, Robert Hildebrand, Renan Lopes, Matthew Pierson We examine the impact of various objective functions on redistricting results, especially compactness. Tradeoffs between compactness and racial equity are examined visually. The ability of partisan gerrymanders to pass visual and analytical compactness tests is explored for Southern states. Methodology includes hill climbing with network techniques used to achieve and maintain feasibility. Cluster analysis is used to compare results of multiple hill-climbing replications. Hill-climbing results are compared to bounds from a stylized non- spatial Karush-Kuhn-Tucker analytical model. WE17 CC Room 202A In Person: Distributed energy generation General Session Chair: Alexandra M Newman, Colorado School of Mines, Colorado School of Mines, Golden, CO, 80401-1887, United States 1 - Balancing Cost and Resilience: Distributed Energy System Design And Dispatch Jamie Grymes, MS, Colorado School of Mines, Golden, CO, 80401, United States As the frequency and duration of grid outages increase, backup power systems are becoming more important for ensuring critical infrastructure can continue to provide essential services. Distributed energy resources such as solar, storage, and combined heat and power are increasingly common sources of onsite power generation. However, a system sized to maximize economic savings may be insufficient to sustain the critical load for an extended outage. In this work, we solve a multi-objective mixed integer linear program to explore the tradeoffs between cost and resilience. 2 - Optimizing Design and Dispatch of a Renewable Energy System with Combined Heat and Power: A Case Study of South Africa Jusse Hirwa, MS, Colorado School of Mines, Golden, CO, 80401, United States, Alexander Zolan, Tulay Flamand, William Becker Lack of access to reliable energy is a major concern for countries in sub-Saharan Africa. Users therefore turn to distributed generation in the form of back-up generators to remain operational in the event of an outage. However, the design of such systems is usually based on rules of thumb. Our optimization model incorporates means of energy supply, in addition to existing on-site technologies, such as renewable energy, combined heat and power, and storage technologies. We examine a hospital in South Africa with requirements of highly reliable electrical and thermal energy supply.

WE08 CC Room 303C In Person: Parallel Server Systems General Session Chair: Gal Mendelson, Stanford Graduate School of Business, Adi, 1794000, Israel 1 - Heavy-traffic Universality of Redundancy Systems with Data Locality Constraints Ellen Cardinaels, Eindhoven University of Technology, Eindhoven, Netherlands, Sem Borst, Johan S. van Leeuwaarden Heterogeneity and compatibility relations between jobs and servers are becoming ubiquitous in cloud computing platforms due to data locality and network topology constraints. These features strongly diverge from the inherent symmetry of the supermarket model as the baseline scenario for performance benchmarking in parallel-server systems. In this talk we will specifically focus on redundancy scheduling systems with compatibility constraints to gain insight from product- form distributions via a heavy-traffic limit. The asymptotics reveal a striking universality property, in the sense that the system achieves complete resource pooling and exhibits the same behavior across a broad range of scenarios. In particular, the performance of a fully flexible system can asymptotically be matched even with quite stringent compatibility constraints. 2 - Stability Properties of Parallel Server Systems under State Dependent Policies Gorkem Unlu, Booth School of Business, The University of Chicago, Chicago, IL, 60615, United St ates , Yuan Zhong We consider the X-Model parallel server system and examine its stability properties under state dependent policies. State dependent policies are attractive because they require only the queue size information. However, they can lead to instability for relatively low system loads. For the X-Model system, we show that switching curve policies, where each server makes the service decision according to a non-decreasing function of queue sizes, can lead to instability. We conjecture that there does not exist a state dependent policy that stabilizes all underloaded parallel server systems. 3 - Asymptotic Optimality of Approximation Based Load Balancing Gal Mendelson, Stanford Graduate School of Business, Palo Alto, CA, 1794000, United States Recent work has shown that using queue length approximations to inform load balancing decisions in systems with multiple dispatchers and parallel servers can lead to excellent performance with a small amount of communication. We consider a general time varying model of such systems and provide a sufficient condition on the approximations under which the queue lengths equalize in the diffusion scale limit. This, in turn, implies that the workload in the system is minimized yielding asymptotic optimality. We analyze several low communication approximation schemes and prove that the resulting approximations satisfy the sufficient condition. WE09 CC Room 303D In Person: Local Algorithms for Dynamic Optimization in Networks Joint Session Chair: Yash Kanoria, Columbia University, Cambridge, United States Co-Chair: Judy Gan, Columbia University, New York, NY, 10027-6945, United States 1 - PTAS for the Optimal Policy in Online Stochastic Combinatorial Optimization Yilun Chen, Cornell, Ithaca, NY, 14850-1854, United States Recently, Chen and Goldberg devised the first polynomial time approximation scheme (PTAS) for high-dimensional optimal stopping, and left open whether the approach could be applied to other high-dimensional stochastic control problems. We present an interesting extension to a natural online high-dimensional combinatorial optimization problem, developing a PTAS (polynomial in the time horizon for any fixed error tolerance and degree) for online stochastic max weight independent set in bounded-degree bipartite graphs. Our approach allows for generally correlated weights, exhibits an interesting correlation decay property, and suggests that the framework may be more broadly applicable. 2 - Know Thy Neighbor: Local Algorithms for Network MDPs Yuanling Gan, Columbia University, New York, NY, United States, Yash Kanoria, Xuan Zhang Motivated by large-scale online marketplaces and other applications, we introduce a benchmark model for dynamic decision-making in networks with future uncertainty. The controller makes a decision at each node in a network at each time. Nodes and edges have associated random reward functions at each time and stochastic (with known distribution) future reward functions. A decision

174