![Show Menu](styles/mobile-menu.png)
![Page Background](./../common/page-substrates/page0389.png)
INFORMS Nashville – 2016
387
WA69
Old Hickory- Omni
Joint Session Telecom/MIF: Modeling and
Optimization for Social Network Analysis
Sponsored: Telecommunications/MIF
Sponsored Session
Chair: Eli Olinick, Southern Methodist University, P.O. Box 750100,
Dallas, TX, 75275, United States,
olinick@lyle.smu.edu1 - Design Of Survivability Networks Under Vulnerability Constraints
Luis Gouveia, University of Lisbon,
legouveia@fc.ul.pt,
Markus Leitner
We consider the Network Design Problem with Vulnerability Constraints
(NDPVC) which simultaneously addresses resilience against failures and bounds
on the lengths of each communication path. We show how the new problem
differs from the Hop-Constrained Survivable Network Design Problem. We
explain that the reason for this difference is that hop-constrained Mengerian
theorems do not hold in general. Three graph theoretical characterizations of
feasible solutions to the NDPVC are derived and used to propose integer linear
programming formulations that are compared in a computational study.
2 - Characterizing Cohesive Subgroups In Social Networks
Zeynep Ertem, university of Texas at Austin, Austin, TX,
United States,
ertem@utexas.edu, Zeynep Ertem, University of
Texas at Austin, Austin, TX, United States,
ertem@utexas.edu,Sergiy Butenko, Alexander Veremyev, Yiming Wang
Identifying closely-knit groups of entities within complex systems might reveal
interesting social circles. In this talk, we first introduce a new mathematical model
that corresponds to a new definition for cohesive subgroups based on a
commonly used graph metric, clustering coefficient. We develop a network-
clustering algorithm using this new model. Second, we develop exact and
approximate algorithms for a special case of our first model, for which two
classical canonical problems (i.e., maximum independent set and maximum
clique) are lower bounds.
3 - The 2-club Polytope
Illya Hicks, Rice University,
ivhicks@rice.edu, Foad Pajouh,
Balabhaskar Balasundaram
Given some positive integer k, a k-club of a graph G is a subset of its vertices S
such that the subgraph induced by S, say G[S], has diameter at most k. The
concept of k-clubs is one of many known relaxations of the concept of cliques for
graphs. The k-club model is particularly interesting from a polyhedral point of
view since it does not posses the hereditary property for k values larger than one.
In this talk, we explore the 2-club polytope and derive facets related to distance
domination. We also present some computational results displaying the
effectiveness of these new inequalities. This is joint work with Foad Pajouh and
Balabhaskar Balasundaram.
4 - A Network Flow Duality Foundation For Hierarchical
Cluster Analysis
Eli Olinick, Southern Methodist University,
olinick@lyle.smu.eduMany popular data clustering and classification techniques from the social
sciences lack a rigorous foundation in graph theory and mathematical
optimization even though they are often based on graph and network models of
interaction and affinity. We show that a clustering method based on the
fundamental graph-theoretic concept of density and implemented via a duality to
network flows can produce more comprehensive and meaningful results in
appropriate problem domains.
WA70
Acoustic- Omni
Transportation, Ops I
Contributed Session
Chair: Markus Matthaus Frey, Dr., Technical University Munich,
Arcisstrasse 21, Munich, 80333, Germany,
markus.frey@tum.de1 - A Simulation-based Optimization Framework For Online Urban
Traffic Control Problems
Linsen Chong, Massachusetts Institute of Technology,
77 Massachusetts Avenue, Room 1-245, Cambridge, MA, 02139,
United States,
linsenc@mit.edu,Carolina Osorio
We propose an online simulation-based optimization (SO) framework that uses
computationally expensive microscopic simulators for real time traffic control
problems. The framework consists of a metamodel SO method, a data-fed
analytical traffic model method and a data-driven method. This framework is
computationally efficient and allows a high-dimensional non-linear optimization
problem to be solved in real time. We illustrate the performance of the proposed
method through a large-scale urban traffic responsive control case study.
2 - Spatial-temporal Air Quality Mapping For Smart-in Vehicle Climate
Control Management
Yimin Liu, Ford Motor Company, Dearborn, MI, United States,
yliu59@ford.com, Yu Chen, Jinjing Yang, Yun-Jhong Wu
The proliferation of connected car technologies with App and cloud-based
analytics provided opportunities for effective vehicle climate control
management. To enable the technologies, we propose an advanced spatial-
temporal model to forecast a high resolution air pollution map fusing existing
government data with the data from vehicle external sensors. Furthermore, an
optimization algorithm is developed to manage in-vehicle air quality at the
optimal level during the trip via the technology.
3 - Road Pricing For Informed Users With Risk Neutral Time Cost
And Risk Averse Health Cost
Zhen Tan, Cornell University, 314 University Ave., Apt 7,
Ithaca, NY, 14850, United States,
zt78@cornell.eduWe analyze tolling for road users with differentiated trip value and delay and
health cost incurred by congestion. Users are informed with delay and pollutant
exposure level. We assume users are risk-neutral to delay but risk-averse to toxic
air inhalation. The linear delay disutility has a multiplier increasing in the trip-
value, while user’s disutility function of inhalation has absolute risk-aversion
decreasing in trip-value. Based on properties of steady-state volume-
delay/inhalation relationships, we characterize the welfare /revenue maximizing
price for one bottleneck and for one prioritized route among two. We discuss on
how health information affects congestion management.
4 - Using Optimization To Improve The Freight Transportation
Operations Of A Fedex Licensee
Omar Ben-Ayed, Qatar University, College of Business and
Economics, Doha, Qatar,
omar.benayed@qu.edu.qa,Salem Hamzaoui, Leandro C Coelho
We describe the applications of network design and timetabling optimization to a
major freight transportation company in the MENA region in order to improve its
performance in terms of cost and delivery time. The application involved two
sequential projects. The first developed and implemented new design and new
timetable that led to remarkable gains for the company. Later, the second project
involved devising better optimization models, obtaining more accurate data, and
more importantly establishing a broader cooperation with the practitioners,
mostly thanks to the trust gained after the success of the first project. Again, the
implementation of our results led to significant improvements.
5 - Column Generation For Vehicle Routing Problems With
Synchronization Constraints
Markus Matthaus Frey, Dr., Technical University Munich,
Arcisstrasse 21, Munich, 80333, Germany,
markus.frey@tum.de,
Martin Fink, Ferdinand Kiermaier, Francois Soumis,
Guy Desaulniers, Rainer Kolisch
Synchronization of workers and vehicles plays a major role in many industries
and belongs to the class of vehicle routing problems with multiple
synchronization constraints (VRPMSs). We present a VRPMSs archetype covering
all synchronization types including movement and load, and propose two
mathematical formulations to efficiently model all synchronization types.
Additionally, we develop a column generation approach employing a novel fixing
strategy.
WA71
Electric- Omni
Game Theory I
Contributed Session
Chair: Jian Yang, Associate Professor, Rutgers University,
1 Washington Park, Rm 1084, Newark, NJ, 7102, United States,
jyang@business.rutgers.edu1 - A Unified Framework For Vehicle Licenses Allocation
Zhou Chen, Hong Kong University of Science and Technology,
Clear Water Bay, Hong Kong, Hong Kong,
zchenaq@connect.ust.hk, Qi Qi, Changjun Wang
Recently, many big cities began to adopt the vehicle licenses quantitative control
policies. In these cities, a limited number of licenses are allocated every month.
The current allocation policies differ from city to city. In this work, we propose to
target the dual objectives of efficiency and equality and present a two-stage
framework that unifies most current mechanisms and outperforms all existing
mechanisms in both efficiency and equality. The unified framework also leads to
easy implementation due to its truthfulness, distribution-free and highly
efficiency. Furthermore, we extend our unified framework into multiple stages
and fully characterize the optimal mechanism.
WA71