2016 INFORMS Annual Meeting Program

WD77

INFORMS Nashville – 2016

WD77 Legends E- Omni Opt, Large Scale II Contributed Session

are their natural extension to sets of multiple instances. We show how to build an m-tttplot from the individual tttplots for each instance in the set and we illustrate several case studies to illustrate the applicability and usefulness of the newly proposed m-tttplots tool. 2 - Guided Tabu Algorithm For Parallel Optimization Hesam Shams, PhD Student, University of Tennessee, 851 Neyland Drive, 525 John D Tickle Engineering Building, Knoxville, TN, 37996, United States, hshams@vols.utk.edu, Oleg Shylo We consider a large class of optimization algorithms that explore solution space by moving from one solution to another via some local neighborhood structure. To enhance the performance of such techniques, we explore effective and scalable methods for storing information about visited solutions to guide future search steps. In particular, we investigate an extension of the tabu search methodology by integrating a long term memory with tabu list dynamics. The proposed algorithm and its parallel version was tested on well-established benchmark instances of job shop scheduling and max-cut problems revealing excellent computational performance. 3 - Heuristics For The Steiner Traveling Salesman Problem Celso C Ribeiro, Universidade Federal Fluminense, Rio de Janeiro, Brazil, celso.ribeiro@gmail.com, Ruben Interian Given a weighted undirected graph and a set of required vertices, the Steiner traveling salesman problem seeks a minimum weighted closed walk on the graph that visits all required vertices. Since a walk is sought, some vertices may be visited more than once. Similarly, some edges may be traversed more than once. We describe a set of benchmark instances and present numerical results obtained with a GRASP heuristic developed for this problem. 4 - Statistical Bounds For Grasp Heuristics Of Np-hard Problems Mengjie Han, PhD, Dalarna University, Högskolan Dalarna, 791 88 Falun, Sweden, Falun, 791 88, Sweden, mea@du.se, Kenneth Carling This work aims at providing statistical bounds for Greedy Randomized Adaptive Search Procedures (GRASP) to NP-hard problems. The quality of the solution to the NP-hard problems is always difficult to be evaluated due to the pre-set the number of iterations. The studies of suggesting statistical bounds as evaluation methods are rare. Thus, we propose the statistical estimator with confidence intervals for GRASP heuristics where four classical NP-hard problems are tested. We also suggest examining a new statistic SR for a stopping rule as a complimentary criteria when probabilistic stopping rules are used. 5 - Optimal Shelf Space Allocation And Inventory Planning For Fresh Produce In Retail Store Hasmukh Gajjar, Associate Professor, Indian Institute of Management Indore, Rau-Pithampur Road, C#208, Prabandh Shikhar, Indore - Madhya Pradesh, 453331, India, hasmukh@iimidr.ac.in, Bhavin J. Shah We consider the stock-dependent demand for fresh produce in a retail store. This paper formulates a mathematical model for joint optimization of shelf space allocation and inventory replenishment. WD79 Legends G- Omni Opt, Combinatorial II Contributed Session Chair: Prasanna Ramamoorthy, IIM Ahmedabad, Vastrapur, Ahmedabad, 380015, India, prasannar@iima.ac.in 1 - An Exact Algorithm For The Covering Capacitated Vehicle Routing Problem Christopher John Wishon, Arizona State University, Tempe, AZ, United States, cwishon@asu.edu, J. Rene Villalobos The Covering Capacitated VRP is similar to the traditional VRP except customers can have their demand serviced by a vehicle stopping at a nearby location assuming that the visited location is within the predetermined service radius of the customer seeking service. This problem is applicable to many VRP applications including the planning of emergency services and mobile retailers. An exact solution method is presented based on the set covering formulation. A branch- and-price methodology was employed and feasible covering routes were generated as needed. The algorithm was tested on existing data sets with the results demonstrating the technique was able to solve problems with up to 50 customers.

Chair: Helder Inacio, Sabre Holdings Inc, 3150 Sabre Drive, Southlake, TX, 76092, United States, Helder.Inacio@Sabre.com 1 - Inexact Block Coordinate Descent Methods For Symmetric Nonnegative Matrix Factorization Haoran Sun, Iowa State University, Ames, IA, United States, hrsun@iastate.edu, Qingjiang Shi, Songtao Lu, Mingyi Hong, Meisam Razaviyayn Symmetric nonnegative matrix factorization (SNMF) is equivalent to computing a symmetric nonnegative low rank approximation of a data similarity matrix. It inherits the good interpretability of the NMF technique and performs better on nonlinearly separable data. In this paper, we focus on the algorithmic aspect of the SNMF problem and propose simple inexact block coordinate decent methods, leading to both serial and parallel algorithms. The proposed algorithms have guaranteed stationary convergence and can efficiently handle large-scale and/or sparse SNMF problems. Extensive simulations verify the effectiveness of the proposed algorithms compared to recent state-of-the-art algorithms. Multivariate Gaussian Random Fields To Large Data Sets Sam Davanloo, The Ohio State University, Columbus, OH, United States, sdt144@vt.edu, Necdet Serhat Aybat, Enrique Del Castillo This paper generalizes the Sparse Precision matrix Selection (SPS) algorithm, proposed by Davanloo et al. (2015),for estimating scalar Gaussian Random Field (GRF) models, to the multivariate, second-order stationary case under a separable covariance function. Theoretical convergence rates for the estimated covariance matrix and for the estimated parameters of the correlation function are established. Numerical simulation results validate our theoretical findings. Data segmentation is used to handle large data sets. 2 - Generalized Sparse Precision Matrix Selection For Fitting 3 - Large Scale Distributed Hessian-free Optimization For Deep Neural Network Xi He, Lehigh University, 837 Cedar Hill Drive, Allentown, PA, 18109, United States, xih314@lehigh.edu, Martin Takac It is well known that the optimization problem derived from deep neural network is always in high dimension with high non-convexity. In this paper, we revisit Hessian-free optimization method for deep network and develop its distributed variant which can utilize computing cluster to train large models. Furthermore, we propose new algorithm to explore negative curvature direction by solving the subproblem with BICGSTAB method involving possible indefinite true batch Hessian information. We show that these techniques accelerate the training process of deep neural network and sharing considerable speed-up by increasing number of nodes. Recovery Problem Helder Inacio, Sabre Holdings Inc, 3150 Sabre Drive, Southlake, TX, 76092, United States, Helder.Inacio@Sabre.com, Chunhua Gao, Ramakrishna Thiruveedhi Airline Crew Recovery can greatly reduce impact caused by disruptions by assigning new rosters to crew. We compare different approaches that can be used to solve this problem. The first approach is optimization based and is focused on reducing overall cost by exploring all recovery options. Other heuristic approaches focus on obtaining fast solutions but have limited search space. We analyze the quality of solutions obtained by using different strategies. We compare the benefits and drawbacks of using these in real-time recovery. The comparisons are made on realistic scenarios of varying size and type of disruption. WD78 Legends F- Omni Opt, Metaheuristics Contributed Session Chair: Hasmukh Gajjar, Associate Professor, Indian Institute of Management Indore, Rau-Pithampur Road, C#208, Prabandh Shikhar, Indore - Madhya Pradesh, 453331, India, hasmukh@iimidr.ac.in 1 - Building And Exploring Multiple Time-to-target Plots (m-tttplots) To Compare Randomized Algorithms Celso C Ribeiro, Full Professor, Universidade Federal Fluminense, Rio de Janeiro, Brazil, celso.ribeiro@gmail.com, Alberto Reyes Time-to-target plots (tttplots) for each problem instance are a useful tool to characterize, evaluate, and compare the behavior of randomized heuristics for combinatorial optimization problems. Multiple time-to-target plots (m-tttplots) 4 - Comparing Different Approaches To Solve Airline Crew

480