2016 INFORMS Annual Meeting Program

431 / 561

INFORMS Nashville – 2016
431
3 - An MDD-based Approach For The Time-dependent TSP
Tallys Yunes, University of Miami, ,
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, , 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,
1 - Solving Large Batches Of Linear Programs
Ilbin Lee, Georgia Institute of Technology, Atlanta, GA, 30332,
United States, 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,
, 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, ,
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-
, 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.
WC14
104D-MCC
Transportation and Disaster Analytics
Sponsored: Analytics
Sponsored Session
Chair: Samiul Hasan, CSIRO, Highett, Australia,
1 - Analyzing Complex Social Contagion During Hurricane Sandy
Using Social Media Communication Data
Arif Mohaimin Sadri, Purdue University, West Lafayette, IN,
United States, , 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,
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,
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,
1 - Understanding Non-convex Optimization For Matrix Completion
Ruoyu Sun, Stanford University,
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).
WC15