Informs Annual Meeting 2017

SA82

INFORMS Houston – 2017

SA83

2 - Learning Preferences with Side-information: Near Optimal Recovery of Tensors Andrew A. Li, MIT, Cambridge, MA, 02139, United States, aali@mit.edu, Vivek Farias Many recent problems in e-commerce can be cast as large-scale problems of tensor recovery. Thus motivated, we study the problem of recovering tensors from their noisy observations. We provide an efficient algorithm to recover structurally ‘simple’ tensors given noisy observations of their entries; our version of simplicity subsumes low rank tensors for various definitions of tensor rank. Our algorithm is practical for massive datasets and provides a significant performance improvement over incumbent approaches to Tensor recovery. Further, we show a near-optimal recovery guarantee. Experiments on music streaming data demonstrate the performance and scalability of our algorithm. 3 - Stochastic Online Scheduling on Unrelated Machines Varun Gupta, University of Chicago, guptav@uchicago.edu, Benjamin Moseley, Marc Uetz, Qiaomin Xie We derive the first performance guarantees for a combinatorial online algorithm that schedules stochastic, nonpreemptive jobs on unrelated machines to minimize the expectation of the total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case, and required sophisticated linear or convex programming relaxations for the assignment of jobs to machines. Our algorithm is purely combinatorial, and therefore it also works for the online setting. 4 - Robust Markov Decision Processes under Non-rectangular Uncertainty Julien Grand-Clement, Columbia University, New York, NY, United States, jg3728@columbia.edu, Vineet Goyal Markov decision processes are a common paradigm for modeling dynamic optimization problems. We consider a robust approach to Markov decision processed where the uncertainty in probability transitions is modeled using an uncertainty set. Most prior works consider the case of uncoupled uncertainty (or rectangular uncertainty) between different states, potentially resulting in highly conservative policies. The general coupled uncertainty set leads to intractable formulations. In this work, we consider a natural low-rank coupled uncertainty between different states and show that this leads to a tractable approach and overcomes the conservativeness of using uncoupled uncertainty sets. 382B New Directions in Stochastic Inventory Control Sponsored: Optimization, Optimization Under Uncertainty Sponsored Session Chair: Cong Shi, University of Michigan, 1205 Beal Ave., Ann Arbor, MI, 48105, United States, shicong@umich.edu 1 - Inventory Management with Opaque Products Yeqing Zhou, Columbia University, 550 W. 120th St, New York, NY, 10027, United States, yz2714@columbia.edu, Adam Elmachtoub, David D.Yao We study the use of opaque products in a multi-item inventory system. An opaque product is defined as a product where some specific attributes are not revealed to customers until after payment. We derive the optimal opaque fulfillment policy which minimizes the long run average inventory costs and show that a simple heuristic is near-optimal for managing opaque products. We also quantify the cost savings achieved by having opaque products (versus not having them) using a connection to the balls-into-bins framework. 2 - Nonparametric Learning Algorithms for Stochastic Inventory Systems with Random Capacities Weidong Chen, PhD Student, Michigan Engineering, Ann Arbor, MI, 48105, United States, aschenwd@umich.edu We propose a nonparametric learning algorithm for the single-product, periodic- review, backlogging inventory systems with random production capacities. We assume that the firm has no prior information on the demand distribution nor the capacity distribution and only has access to past demand and supply data (which can be referred to as censored capacity information). We propose a cyclic gradient-descent type of algorithm whose running average cost asymptotically converges to the clairvoyant optimal costWe prove that the rate of convergence guarantee of our algorithm is O(\sqrt{T}), and conduct numerical experiments to demonstrate the effectiveness of our proposed algorithms. 3 - Online Algorithms for Stochastic Inventory Systems Yuchen Jiang, University of Michigan, Ann Arbor, MI, 48109, United States, ycjiang@umich.edu We study stochastic inventory systems by designing online algorithms to determine optimal inventory decisions before the realization of any future demands. Our online algorithm uses up-to-date demand information and hence can be carried out in practice. Moreover, our competitive analysis shows that the algorithms we proposed preform well even in the adversarial setting, where the worst case demand realization is considered. SA82

382C Sequential Decision Making under Uncertainty Sponsored: Optimization, Optimization Under Uncertainty Sponsored Session Chair: Belleh Fontem, University of Mary Washington, Fredericksburg, VA, 22407, United States, bfontem@umw.edu 1 - Multi-objective Sequential Stochastic Assignment Problems Ge Yu, University of Illinois, Champaign, IL, United States, geyu3@illinois.edu, Sheldon Jacobson We provide an asymptotic analysis of multi-objective sequential stochastic assignment problems (MOSSAP). In MOSSAP, a fixed number of tasks arrive sequentially, with an n-dimensional value vector revealed upon arrival. Each task is assigned to one of a group of known workers immediately upon arrival, with the reward given by an n-dimensional product-form vector. The objective is to maximize each component of the expected reward vector. We provide expressions for the asymptotic expected reward per task for each component of the reward vector, under three classes of Pareto optimal policies. We also compare the convergence rates of these three classes of Pareto optimal policies. 2 - Concentration Inequality Approach to Variance-Constrained Bivariate Optimal Stopping Belleh Fontem, University of Mary Washington, Fredericksburg, VA, United States, bfontem@umw.edu Under a certain payoff structure, we consider the problem of finding an optimal stopping time for a bivariate random walk subject to a constraint on the stopping variance of one of the state variables. The non-linearity of the variance constraint gives rise to time-inconsistency in the sense that traditional Bellman optimality is inapplicable. We employ two concentration inequalities to prove optimality of the first-exit time of the relevant state variable from either a control band, or a half- space (depending on the how we interpret optimality). The motivating application is determining an optimal selling policy for a risk-averse rental car firm that also serves purchasing customers. Sunday Plenary GBCC- General Assembly B, Level 3 The Final Step in the Remarkable Journey of the Isoperimetric Problem: The Completion of Euler’s Approach Plenary Invited Session 1 - The Final Step in the Remarkable Journey of the Isoperimetric Problem: the Completion of Euler’s Approach Richard Tapia, Rice University In this presentation we give a brief overview of the remarkable life of the impactful isoperimetric problem. We identify three distinct classes of solution approaches that have been used throughout history: the Cartesian coordinate representation approach of Euler, the synthetic geometry approach of Steiner, and the parametric representation approach of Weierstrass. We say that one of our three classes of approaches has been completed when an appropriately short sufficiency proof for the isoperimetric problem has been constructed that belongs to this class of proofs. In a legendary work from 1744, Euler presented his contribution, establishing neither necessity nor sufficiency for this problem. This failure led Steiner in 1838 to propose his approach that gave only necessity and not sufficiency as he believed. The Steiner path was completed by Lawlor in 1998. Euler’s and Steiner’s failures led Weierstrass in 1879 to propose his approach, which did indeed lead to sufficiency but required a somewhat elaborate theory. The Weierstrass approach was completed in 1934 by Littlewood, Hardy, and Polya. The major contribution in this presentation is our completion of Euler’s approach. Our proof uses elementary tools. Sunday, 10:00 - 10:50AM

32