INFORMS 2021 Program Book

INFORMS Anaheim 2021

TB02

conditional risk measures, we provide tight lower bounds for the gaps between optimal objective values of the risk-averse multistage and two-stage models. Moreover, two approximation algorithms are proposed to solve the programs efficiently, with the approximation ratio independent of the underlying stochastic process, structure of the scenario tree, and risk parameters. Computational studies are conducted on randomly generated and real network instances to demonstrate the tightness of the bounds and efficacy of the approximation algorithms. TB03 CC Ballroom C / Virtual Theater 3 Hybrid Design and Operation of Online Platforms Sponsored: Auctions and Market Design Sponsored Session Chair: Daniela Saban, Stanford University, Aachen, United States Co-Chair: Vahideh Manshadi, Yale University, New Haven, CT, United States 1 - Designing Service Menus for Bipartite Queueing Systems Varun Gupta, University of Chicago Booth School of Business, Chicago, IL, 60637-1610, United States, Rene A. Caldentey, Lisa Hillas We look at the problem of designing a matching system with queues in an environment with multiple classes of servers, and multiple types of customers with heterogeneous preferences over servers. The system designer offers a static menu of service classes, where each menu is a set of servers that can serve the service class. Customers choose which class to join upon arrival. The servers serve their adjacent service classes in First-Come-First-Served order. Customers act as rational self-interested utility maximizing agents when choosing which service class to join. We study the problem under (conventional) heavy traffic conditions, that is, in the limit as the traffic intensity of the system approaches one from below, and provide insights into the design tradeoffs of “good” service menus. 2 - In Which Random Matching Markets Does the Short Side Enjoy an Advantage? Pengyu Qian, Purdue University, Krannert School of Management, Columbia Business School, West Lafayette, IN, 10027, United States, Yash Kanoria, Seungki Min In this work, we study Gale-Shapley two-sided matching markets where agents on both sides have ordinal preferences over potential partners on the other side. These markets have broad applications in school choice, labor markets, etc.We investigate in which markets does being on the short side of the market allow agents to obtain better match partners relative to a similar ``balanced’’ market with equal numbers of agents on the two sides.We study ``partially connected’’ random matching markets with n+k men and n women in which agents consider a limited set of potential partners, and discover a new type of smoking gun evidence of whether a matching market exhibits a short side advantage. In particular, we sharply characterize the resulting (nearly unique) stable matching as a function of the connectivity d and the ``imbalance’’, overcoming significant technical challenges. 3 - Designing Approximately Optimal Search On Matching Platforms We study the design of a two-sided matching market in which agents’ search is guided by a platform. The platform determines the rates at which agents of different types meet, while agents strategically accept or reject the potential partners whom they meet. We focus on the platform’s problem of optimal search design in a continuum matching market model where agents have symmetric pairwise preferences. The platform’s objective is to find meeting rates that maximize the equilibrium social welfare of the resulting game. Incentive issues arising from congestion and cannibalization make this design problem intricate. Nonetheless, we give an efficiently computable solution that achieves 1/4 the optimal social welfare. Our solution shows the platform can substantially limit choice while maintaining approximately optimal welfare through a carefully chosen search design. 4 - The Value of Excess Supply in Spatial Matching Markets Yeganeh Alimohammadi, Stanford University, Stanford, CA, United States, Mohammad Akbarpour, Shengwu Li, Amin Saberi We study dynamic matching in a spatial setting. Drivers are distributed at random on some interval. Riders arrive in some (possibly adversarial) order at randomly drawn points. The platform observes the location of the drivers, and can match newly arrived riders immediately, or can wait for more riders to arrive. The cost of matching a driver to a rider is equal to the distance between them. We quantify the value of slightly increasing supply. We prove that when there are $(1+\epsilon)$ drivers per rider (for any $\epsilon > 0$), the cost of matching returned by a simple greedy algorithm which pairs each arriving rider to the closest available driver is $O(\log^3(n))$, where $n$ is the number of riders. However, with equal number of drivers and riders, even the ex post optimal matching does not have a cost less than $\Theta(\sqrt{n})$. Alexander Wei, UC Berkeley, Berkeley, CA, United States, Nicole Immorlica, Brendan Lucier, Vahideh Manshadi

TB02 CC Ballroom B / Virtual Theater 2 Hybrid Stochastic or Distributionally Robust Integer Programming Sponsored: OPT/Optimization Under Uncertainty Sponsored Session Chair: Xian Yu, University of Michigan, Ann Arbor, MI, 48105-2129, United States Co-Chair: Siqian Shen, University of Michigan, Ann Arbor, MI, 48109- 2117, United States 1 - Rolling Horizon Policies in Multistage Stochastic Programming Murwan Siddig, Clemson University, Clemson, SC, United States, Yongjia Song, Amin Khademi Multistage Stochastic Programming (MSP) is a class of models for sequential decision-making under uncertainty. MSP problems are known for their computational intractability due to the sequential nature of the decision-making structure and the uncertainty in the problem data due to the curse of dimensionality. A common approach to tackle MSP problems with a large number of stages is a rolling-horizon (RH) procedure, where one solves a sequence of MSP problems with a smaller number of stages. This leads to a delicate issue of how many stages to include in the smaller problems used in the RH procedure. This paper addresses this question for, both, finite and infinite horizon MSP problems. Our numerical experiments on a hydrothermal power generation planning problem show the effectiveness of the proposed approaches. 2 - Stochastic Routing and Wavelength Assignment Problem in WDM Networks Maryam Daryalal, University of Toronto, Toronto, ON, Canada In a telecommunication network, Routing and Wavelength Assignment (RWA) is the problem of finding a path and a wavelength for every incoming request. In the first part of this talk we introduce the first two-stage stochastic integer programming model for the RWA problem with incoming request uncertainty, to maximize the expected number of granted requests. We design a decomposition- based solution approach, which uses various relaxations of the problem and a newly developed cut family. Guided by the multistage nature of the provisioning decisions, in the second part of the talk we present a multistage model for the RWA problem with incremental traffic. Evaluating obtained solutions in a multistage setting in a rolling-horizon framework, we show that our methods provide high-quality solutions compared to traditionally used deterministic ones. 3 - Pragmatic Distributionally Robust Optimization for Simple Integer Recourse Models Ruben van Beesten, MSc, University of Groningen, Groningen, Netherlands, David Morton, Ward Romeijnders We consider simple integer recourse (SIR) models under distributional uncertainty. Distributionally robust optimization (DRO) provides a framework for dealing with the distributional uncertainty in these models. However, the integer restrictions typically cause these models to be non-convex and hence, hard to solve. To overcome this issue, we propose a pragmatic approach in which we restrict the uncertainty set in such a way that the problem becomes convex, while the uncertainty set remains structurally similar to traditional uncertainty sets. We coin this approach pragmatic DRO.In this presentation we focus on a setting where the uncertainty set is based on a set of moment conditions. We show that our pragmatic approach is equivalent to a continuous recourse problem under modified moment conditions. 4 - On Finite Adaptability in Two-stage Distributionally Robust Optimization Eojin Han, Southern Methodist University, Dallas, TX, 75205, United States, Chaithanya Bandi, Omid Nohadani In many applications, practitioners prefer policies that are interpretable and easy to implement. In this paper, we leverage the concept of finite adaptability to construct policies for two-stage distributionally robust optimization problems. This is done by partitioning the uncertainty space and assigning a contingent decision to each piece. We first show that the optimal partitioning can be characterized by translated orthants, which only require the problem structure. We then prove that finding the optimal partitioning is hard and propose a specific partitioning scheme with orthants, which can be obtained by solving a mixed-integer optimization problem of a moderate size. We provide performance bounds of our policies which generalize the existing bounds in the literature. We also assess suboptimality in general settings and provide techniques for lower bounds. 5 - On the Value of Multistage Stochastic Facility Location with Risk Aversion Xian Yu, University of Michigan, Ann Arbor, MI, 48105-2129, United States, Shabbir Ahmed, Siqian Shen We study the capacitated facility location problem over a finite time horizon under uncertain demand. We model a multistage stochastic integer program based on a scenario tree representation and compare it with a two-stage approach that decides which facilities to open for all periods upfront. Using expected

100