INFORMS 2021 Program Book

INFORMS Anaheim 2021

WE22

hardness the general case; in Phase 2, we reallocate revenue via potential-based optimization to guarantee subgame-perfect equilibrium and envy-freeness for drivers. We additionally reduce the stochastic model to the deterministic model to justify its credibility in real-world applications, and show its performance with simulation results. 3 - The Effectiveness of Single Price Change in Learning and Earning via Sequential Estimation Jeunghyun Kim, Korea University, Seoul, 02841, Korea, Republic of, Dongyuan Zhan, Chihoon Lee We study a revenue maximization problem in a congestible system with unknown demand parameters. We show that a single price change during the learning phase is sufficient to obtain a revenue regret that is on the same scale with the optimal regret achievable when demand parameters are known up front. The sufficiency of single price change in learning is due to the implementation of sequential maximum likelihood estimation (SMLE). Without knowledge of demand parameters, an initial price is randomly chosen. With a typical MLE under which a sample size for learning is pre-fixed, the quality of estimation with the randomly chosen price is not controllable, making the choice of the second price as equally uninformative as for the first price. On the other hand, SMLE makes learning with the first price informative as it can control the estimation quality. WE25 CC Room 205B In Person: Combinatorial Optimization Contributed Session Chair: Ian Griffith Ludden, University of Illinois at Urbana-Champaign, Urbana, IL, 61801-6628, United States 1 - Comparison of Local Search Algorithms for Solving Car Sequencing Problem Ibrahim Ozan Yilmazlar, PhD Student, Clemson University, Clemson, SC, United States, Mary Beth Kurz Sequencing varying models in a mixed-model assembly line has the objective of preventing line stoppage resulting from work overload. Consecutive models that require a high amount of work at a station results in an inevitable work overload. The car sequencing problem (CSP) minimizes the work overload by applying capacity rules, resulting in the goal of finding the sequence with the minimum number of capacity rule violations. In this study, a mathematical formulation of the CSP is presented. Additionally, fast and effective Adaptive Local Search (ALS) and Variable Neighborhood Search (VNS) algorithms are proposed to solve respectively larger instances and compared over benchmark instances. 2 - On Small-Depth Tree Augmentations Michael Zlatin, Carnegie Mellon University, Pittsburgh, PA, United States, R. Ravi, Ojas Parekh The Tree Augmentation Problem is a fundamental and intensely studied problem in the area of survivable network design. We show that the integrality gap of the ODD-LP relaxation for the (weighted) Tree Augmentation Problem for a k-level tree instance is at most 2 (1/2)^(k-1). For 2- and 3-level trees, these ratios are 3/2 and 7/4 respectively. Our proofs are constructive and yield polynomial-time approximation algorithms with matching guarantees. 3 - Application of Flexible Flow Shop Scheduling with Sequence Dependent Setup Times in Labeling Industry Sam Heshmati, Lecturer, University of Kentucky, Lexington, KY, United States, Charles R. Sox The flexible flow shop (FFS) is a common manufacturing layout which has applications in many industries. This study considers the FFS with sequence dependent setup times in labeling industry. The case considered by the authors exhibits some of the complexity of the real-life industry. In addition to a mathematical formulation, a fast metaheuristic based on late acceptance hill climbing algorithm is presented. The quality of the proposed approach is compared against the state-of-the-art approaches.The results indicate the significant improvements over current practice in the case study industry. The proposed approach has a general setup which enables the usage of model within other industries. 4 - Combinatorial Optimization Problems in Ising Form: Issues in Using Single-Spin-Flip Local Search Heuristics Ignacio Rozada, 1QBit, Vancouver, BC, Canada, Brad Woods Specialized hardware for solving Ising problems using local search heuristics is being increasingly developed, as many combinatorial optimization problems can easily be reduced to Ising form. However, the usual approach of performing single-flip updates can have serious drawbacks. The Ising form of some problems, like the quadratic assignment and travelling salesman problems, where penalty methods encode constraints, is akin to minimizing an optimization problem with O(n!) local optima separated by high penalty barriers. Consequently, the performance achievable using a single-flip Ising solver is equivalent to randomly drawing feasible configurations in the original solution space.

WE22 CC Room 204B In Person: Optimal Large-scale Policies in Emerging Healthcare Problems General Session Chair: Sohom Chatterjee, Texas A&M University, College Station, TX, 77840, United States 1 - The Impact of Early Large-scale Screening on the Evolution of Pandemics We study the problem of large-scale screening in the early stages of a pandemic. In this setting, resources such as testing kits, budget, and hospital beds are scarce, and early-stage testing has the potential to alter the dynamics of disease spread. Thus, devising optimal screening strategies that operate within these constraints is crucial to saving lives and reducing healthcare costs. To address the issue of limited testing capacity, we study two models that focus on either individual or group (pooled) testing, and we determine conditions under which each scheme is superior. We calibrate our models using data on the ongoing COVID pandemic and demonstrate the benefits of our proposed methods. 2 - Presenter Seth D. Brown, Rice University, Houston, TX, 77098, United States We present a general framework for allocating scarce resources to disparate groups fairly and efficiently. We focus on the example of liver transplant allocation among multiple patient groups. In particular, we show how the parameters of a given patient population can be used to determine a score exception approach which lies on the efficient frontier with respect to each patient’s well-being while taking individual patient agency into account. We provide a two-stage stochastic model whose parametrized recourse function takes the form of a binary linear program which can be solved as an LP. 3 - Capturing the Dilution Effect of Risk-based Group Testing with Application to COVID-19 Screening Sohom Chatterjee, Texas A&M University, College Station, TX, United States, Hrayer Aprahamian In this paper, we construct optimal group testing schemes for heterogeneous populations considering imperfect tests and the dilution effect of grouping. We first conduct an analysis under a general sensitivity dilution function and, since closed-form expressions are not possible, identify a closed-form upper bound which is treated as a proxy objective function and optimized. We then consider a special sensitivity function that is realistic, calibratable, and possesses favorable properties that enable us to reach the global optimum in polynomial time. We illustrate the benefits of this framework using a case-study on recently published dilution data for the COVID-19 PCR test. Our results highlight the importance of incorporating important test and population-level risk characteristics into the modeling framework, as failing to do so can lead to poor outcomes. WE23 CC Room 204C In Person: Learning and Economic Optimization in Stochastic Systems General Session Chair: Jeunghyun Kim, Korea, Republic of 1 - Dynamic Dispatch and Pricing in Ride-Hailing Systems Amir Anastasios Alwan, University of Chicago Booth School of Business, Chicago, IL, 60616-1740, United States, Baris Ata Motivated by ride-hailing systems, we consider a dynamic control problem of a multi-class closed queueing network with infinite-server nodes. Crucially, our model incorporates the travel times between different nodes in the network. The platform seeks to maximize long-run average expected profit by making dynamic dispatch and pricing control decisions. Under heavy-traffic conditions, we approximate the original control problem by a Brownian control problem that leads to an effective policy for the ride-hailing system. 2 - Dynamic Car Dispatching and Pricing: Revenue and Fairness for Ridesharing Platforms Zishuo Zhao, PhD Student, University of Illinois at Urbana- Champaign, Urbana, IL, United States It is essential for ridesharing platforms to balance supply and demand with dynamic prices, but a major challenge is to guarantee profit and fairness simultaneously in the presence of misaligned incentives of drivers and riders. We focus on the problem to maximize the drivers’ revenue while keeping both drivers and riders satisfied via a two-phase mechanism. In Phase 1, we develop a max-weight flow model that theoretically yields maximum revenue for deterministic future orders under a regularity assumption, and prove its NP- Marwan Safwan Shams Eddin, George Mason University, Manassas, VA, 20110, United States, Hadi El-Amine, Hrayer Aprahamian

176