2016 INFORMS Annual Meeting Program

480 / 561

INFORMS Nashville – 2016
480
WD77
Legends E- Omni
Opt, Large Scale II
Contributed Session
Chair: Helder Inacio, Sabre Holdings Inc, 3150 Sabre Drive,
Southlake, TX, 76092, United States,
Nonnegative Matrix Factorization
Haoran Sun, Iowa State University, Ames, IA, United States,
, 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, , 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.
Neural Network
Xi He, Lehigh University, 837 Cedar Hill Drive, Allentown, PA,
18109, United States, , 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, , 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,
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, 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)
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, 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, , 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, ,
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,
, 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,
1 - An Exact Algorithm For The Covering Capacitated Vehicle
Routing Problem
Christopher John Wishon, Arizona State University, Tempe, AZ,
United States, , 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.
WD77
1 - Inexact Block Coordinate Descent Methods For Symmetric
2 - Generalized Sparse Precision Matrix Selection For Fitting
3 - Large Scale Distributed Hessian-free Optimization For Deep
4 - Comparing Different Approaches To Solve Airline Crew