INFORMS 2021 Program Book

INFORMS Anaheim 2021

TC28

3 - Online Task Assignment with Multi-capacity Constraints Liron Yedidsion, Amazon, Seattle, WA, 3491319, United States Striving to satisfy customers’ demands within one day for an increasing variety of products, companies are required to assign operations to resources on any level in the supply chain within minutes of any incoming customer order. These include fulfillment centers, sort centers, delivery stations, carriers, subcontractors, and down to the level of a single route. Each resource has its own capacities of processing time and space. Amazon is required to make decisions in an online and dynamic manner. We present a multidimensional stochastic dynamic program designed for that purpose. TC25 CC Room 205B In Person: Advances in Discrete Optimization General Session Chair: Jongeun Kim, University of Minnesota, Minneapolis, MN, 55414, United States 1 - Heterogeneous Multi-Resource Allocation Problem Arden Baxter, Georgia Institute of Technology, Atlanta, GA, 30309, United States, Pinar Keskinocak, Mohit Singh Motivated by resource allocation settings that may require coordination, we consider the problem of allocating multiple heterogeneous resources geographically and over time to meet demands that require some subset of the available resource types simultaneously at a specified time, location, and duration. The objective is to maximize total reward accrued from meeting (a subset of) demands. We model this problem as an integer program, show it is NP-hard, analyze the complexity of special cases, and introduce approximation algorithms. We further study uncertainty in demand through the stochastic version of the problem using a two-stage stochastic integer program where the first-stage decision determines the number of resources of each type and the second-stage decision initializes resources at starting locations and assigns them to demands. 2 - A Reciprocity Between Tree Ensemble Optimization and Multilinear Optimization Over the Cartesian Product of Simplices Jongeun Kim, University of Minnesota, Minneapolis, MN, 55414, United States, Jean-Philippe P. Richard, Mohit Tawarmalani We study the connection between tree ensemble optimization problem and multilinear optimization over the cartesian product of simplices. We show that two problems are equivalent. We also provide some polyhedral results on a multilinear set that can be used to derive an improved formulation in tree ensemble optimization. TC26 CC Room 206A In Person: Optimization Over Sparse and Low-rank Structures General Session Chair: Ryan Cory-Wright, MIT, Cambridge, MA, 02141-1534, United States 1 - Sparse and Low Rank Matrix Decomposition: A Discrete Optimization Approach Nicholas Andre G. Johnson, United States The Sparse Plus Low-Rank decomposition problem (SLR), or the problem of approximately decomposing a data matrix into a sparse matrix plus a low-rank matrix, arises throughout many fundamental applications in Operations Research, Machine Learning and Statistics. The difficulty of this problem stems from the natural rank and sparsity constraints which are non convex and non smooth. Existing approaches are heuristic in nature, many relying on nuclear norm and L1 norm based convex relaxations, and do not possess optimality guarantees. We introduce a novel formulation for SLR that directly models the underlying discreteness of the problem. For this formulation, we develop an algorithmic approach to solving SLR to certifiable optimality by deriving a strong heuristic, a strong convex relaxation and embedding these within a custom branch and bound routine. 2 - Sparse Quadratic Optimization with Sparse Matrices Peijing Liu, University of Southern California, Los Angeles, CA, United States, Andres Gomez, Simge Kucukyavuz We study problems arising in sparse regression, where additionally the model matrix is sparse. We first show that a class of problems with tridiagonal matrices can be solved efficiently in polynomial time. For problems involving sparse but not tridiagonal matrices, we discuss decomposition approaches using Fenchel duality that leverage sparsity and produce high quality solutions in a fraction of the time required to solve the problems using standard techniques.

3 - KFW: A Frank-wolfe Style Algorithm with Stronger Subproblem Oracles Lijun Ding, Cornell University, Ithaca, NY, 14850-2842, United States This talk proposes a new variant of Frank-Wolfe (FW),called kFW. Standard FW suffers from slow convergence:iterates often zig-zag as update directions oscillate around extreme points of the constraint set. The new variant, kFW, overcomes this problem by using two stronger subproblem oracles. The first is a k linear optimization oracle (kLOO) that computes the k best update directions. The second is a k direction search (kDS) that minimizes the objective over a constraint set represented by the k best update directions and the previous iterate. When the problem solution admits a sparse representation, both oracles are easy to compute, and kFW converges quickly for smooth convex objectives and several interesting constraint sets: kFW achieves finite convergence on polytopes and group norm balls, and linear convergence on spectrahedra and nuclear norm balls. 4 - A New Perspective on Low Rank Optimization Ryan Cory-Wright, MIT, Cambridge, MA, 02141-1534, United States, Dimitris Bertsimas, Jean Pauphilet A key question in many low-rank problems is to characterize the convex hulls of simple low-rank sets and judiciously apply these convex hulls to obtain strong yet affordable convex relaxations. We apply the matrix perspective function —the matrix analog of the perspective function — to characterize explicitly the convex hull of epigraphs of convex quadratic, matrix exponential, and matrix power functions under rank constraints. Further, we exploit these characterizations to develop strong relaxations for a variety of low-rank problems including reduced rank regression and factor analysis. We establish that these relaxations can be modeled via semidefinite, relative entropy, and matrix power cone constraints and thus optimized over tractably. The proposed approach parallels and generalizes the perspective reformulation technique in mixed-integer optimization. TC28 CC Room 207B In Person Technology Tutorial: This IS IT! Interactive Smart Textbooks for the Modern Program! Technology Tutorial 1 - This IS IT! Interactive Smart Textbooks for the Modern Program! Jaret Wilson, MyEducator, Orem, UT, United States, Scotty Pectol This is modern higher education! An affordable alternative to OER with up-to- date content from world-class author teams. Created by professors for professors, MyEducator smart interactive textbooks and learning resources are ideal for any classroom setting and work within live technology environments so your students don’t just learn, they do! Our approach enhances student engagement, improves learning outcomes, instructors receive better teaching evaluations, and students have more fun in the classroom.Each smart learning resource is hosted on our intuitive platform with auto-graded assessments, ample instructor material, robust analytics, all with seamless single sign-on LMS integration, low student cost, lifetime access, and best-in-class service. Full access will be given to any book on our platform to attendees. In Person Technology Tutorial: Turning Models Into Applications– GAMS Engine and GAMS Transfer Technology Tutorial 1 - Turning Models Into Applications- GAMS Engine and GAMS Transfer Steven Dirkse, GAMS. Development Corporation, Fairfax, VA, United States, Adam Christensen The right tools help you deploy your GAMS model and maximize the impact of your decision support application. GAMS Engine is a powerful tool for solving GAMS models, either on-prem or in the cloud. Engine acts as a broker between applications or users with GAMS models to solve and the computational resources used for this task. Central to Engine is a modern REST API that provides an interface to a scalable Kubernetes-based system of services, providing API, database, queue, and a configurable number of GAMS workers. GAMS Transfer is an API (available in Python, Matlab, and soon R) that makes moving data between GAMS and your computational environment fast and easy. By leveraging open source data science tools such as Pandas/Numpy, GAMS Transfer is able to take advantage of a suite of useful (and platform independent) I/O tools to deposit data into GDX or withdraw GDX results to a number of data endpoints (i.e., visualizations, databases, etc.). TC28 CC Room 207B

119