2016 INFORMS Annual Meeting Program

WC15

INFORMS Nashville – 2016

WC14 104D-MCC Transportation and Disaster Analytics

3 - An MDD-based Approach For The Time-dependent TSP Tallys Yunes, University of Miami, tallys@miami.edu, David Bergman, Andre Augusto Cire The Time-Dependent Traveling Salesman Problem (TDTSP) is a variant of the classical Traveling Salesman Problem in which arc-traversal times vary over time, a typical real-life example being rush-hour traffic. We describe a solution approach for the TDTSP using Multivalued Decision Diagrams (MDDs) and present preliminary computational results for a set of known benchmark instances. 4 - Branching With Less Repetition Thiago Serra, Carnegie Mellon University, Pittsburgh, PA, 15213, United States, tserra@cmu.edu, John Hooker When branching to solve a problem on discrete variables, we may reach nodes that will root isomorphic subtrees. Hence, the subproblem from each of such nodes has the same solutions. If we merge those equivalent nodes after they are explored, we get a reduced decision diagram. But if we can anticipate that a new node is equivalent to an explored node, then we keep a reduced decision diagram and prevent redundant work. In this paper, we generalize previous results on constructing a reduced decision diagram for linear contraints, and we extend those results to discrete problems on multiple constraints. We characterize node states and we provide some sufficient conditions to check node equivalence. WC13 104C-MCC Computational Approaches to Large-scale/Exact Optimization Sponsored: Optimization, Computational Optimization and Software Sponsored Session Chair: Ilbin Lee, Georgia Tech, Georgia Tech, Atlanta, GA, 30332, United States, ilee79@gatech.edu 1 - Solving Large Batches Of Linear Programs Ilbin Lee, Georgia Institute of Technology, Atlanta, GA, 30332, United States, ilee79@gatech.edu, Stewart Curry, Nicoleta Serban Solving a large number of linear programs (LPs) with varying parameters is needed in stochastic programming and sensitivity analysis among other modeling frameworks. The common approach is solving each individual LP, called the brute-force approach, which can be computationally infeasible when the parameter space is high-dimensional and/or the underlying LP is computationally challenging. We introduce a computationally efficient approach for solving a large number of LPs in batches and suggest a data-driven version of our algorithm. The experimental results show that our approach can be more efficient and scale better in the number of LPs than the brute-force that uses MATLAB solver. 2 - Bilinear Optimization And Its Application In Robust Optimization Wei Wang, University of Pittsburgh, Pittsburgh, PA, United States, w.wei@pitt.edu, Anna Danandeh, Bo Zeng, Brian Buckley We derive exact and approximated methods to compute bilinear optimization. And we show applications of bilinear optimization in robust optimization. 3 - Efficient Validation Of Basic Solutions Via The Roundoff-error-free Factorization Framework Adolfo R Escobedo, Assistant Professor, Arizona State University, Tempe, AZ, 85281, United States, adolfo.escobedo@asu.edu, Erick Moreno-Centeno The Roundoff-Error-Free (REF) factorization framework solves systems of linear equations without accruing roundoff errors or excessive entry growth, thereby permitting LPs and MIPs to be solved exactly and efficiently. This work discusses results showing that the integer-preserving REF framework is up to two orders of magnitude quicker than the standard-use rational arithmetic LU factorization method while requiring half the memory. Moreover, we adapt Edmond’s integer- preserving Q-Matrices to validate basic solutions, and summarize additional experiments that demonstrate the REF factorization framework remains superior in terms of memory requirements and computational effort. 4 - Computational Study Of Valid Inequalities For A Semidefinite Relaxation Of Maximum-k-cut Miguel F. Anjos, Professor and Canada Research Chair, GERAD & Polytechnique Montreal, Montreal, QC, Canada, miguel- f.anjos@polymtl.ca, Vilmar Rodrigues de Sousa, Vilmar Rodrigues de SousaLe Digabel We present the results of a computational study to identify the best inequalities to tighten a semidefinite relaxation of the maximum-k-cut problem. We focus on four families of inequalities (Clique, General clique, Wheel and Bicycle wheel) and tested them for different values of k using a set of 147 benchmark instances (with nearly equal numbers of dense and sparse). Our results suggest that Bicycle wheel and Wheel are the strongest inequalities for k = 3, and that for k > 3 the Wheel inequalites are the strongest by far.

Sponsored: Analytics Sponsored Session Chair: Samiul Hasan, CSIRO, Highett, Australia, samiul.hasan@gmail.com 1 - Analyzing Complex Social Contagion During Hurricane Sandy Using Social Media Communication Data Arif Mohaimin Sadri, Purdue University, West Lafayette, IN, United States, asadri@purdue.edu, Samiul Hasan, Satish Ukkusuri, Manuel Cebrian Hurricane Sandy was one of the strongest and costliest in the history of hurricanes. Many people used social media to communicate during this period while lacking access to traditional information sources. In this study, we analyzed raw data (~52 M tweets, ~13 M users, Oct 14 -Nov 12, 2012) obtained from Twitter. First, we identify different communities from the subgraph of Twitter that was active before, during, and after Sandy’s landfall. Then, we extract the topics evolved in this subgraph over time. Finally, we examine the relationship between network topology and user activity. 2 - Short-term Taxi Demand Forecasting Accouting For Spatio-temporal Correlations Xinwu Qian, Purdue University, qian39@purdue.edu To improve efficiency of taxi market, we may dispatch taxicabs to specified locations or framing dynamic pricing policies before the reveal of passenger demand. This requires knowledge on spatial taxi demand in immediate future, and is less prone to prediction errors. In this study, we develop a Gaussian Conditional Random Field model to forecast the short-term taxi demand using history time series. The model captures spatio-temporal dependencies, and generates multiple steps ahead probabilistic estimations of short-term taxi demand. The results suggest the superiority of the GCRF model over other methods, with best overall MAPE of 0.117 and being robust for predicting demand under anomalies. 3 - Traffic State Estimation For Arterial Networks Using License-plate Recognition Data Xianyuan Zhan, Purdue University, zhanxianyuan@purdue.edu This study proposes a statistical modeling framework to estimate the network- wide real-time traffic states using License-plate recognition (LPR) data from a subset of intersections. The model operates in two steps: first, the cycle maximum queue lengths are estimated for monitored links (downstream intersections equipped with LPR cameras); second, a Hybrid Dynamic Bayesian Network model is developed to infer the queue length states for unmonitored links as well as the average link travel times for the entire network. A week’s LPR data from 13 intersections in a small road network from Langfang, China are used to test and validate the model. WC15 104E-MCC Exploiting Sparse and Low Rank Structures for Inference Sponsored: Artificial Intelligence Sponsored Session Chair: Meisam Razaviyayn, Stanford University, 275 Ventura Ave, Apt 27, Palo Alto, CA, 94306, United States, meisamr@stanford.edu 1 - Understanding Non-convex Optimization For Matrix Completion Ruoyu Sun, Stanford University, ruoyus@stanford.edu Low-rank matrix completion is usually solved by machine learning practitioners using the non-convex factorization formulation. A natural question is whether a non-convex formulation for matrix completion can be solved to global optima. We provide an affirmative answer to this question by showing that under mild conditions, many standard optimization algorithms converge to the global optima of a factorization formulation, and recover the true low-rank matrix. The high level idea is that the problem exhibits a nice geometrical property, which is why we can provide recovery guarantee for a wide variety of algorithms including SGD (stochastic gradient descent) and BCD (block coordinate descent).

431