2016 INFORMS Annual Meeting Program

46 / 561

INFORMS Nashville – 2016
46
3 - Optimal Design Of A Nation-wide Surveillance System For Early
Detection Of An Invasive Bark Beetle
Rebecca Epanchin-Niell, Resources for the Future,
Surveillance programs for early detection of new invaders can reduce long term
costs by increasing the likelihood of successful eradication and reducing control
and damage costs. We develop a model for allocating surveillance resources based
on expected return on investment, in which resources are targeted first in areas
with the highest expected benefits relative to costs. We define trapping benefits as
the expected reduction in costs from active surveillance (i.e. trapping) relative to
passive surveillance alone. We apply the approach to bark beetle detection
programs in the U.S.
4 - Optimal Control Of Bio-invasions With Eradication Success
Benchmarks And Management Of High Program Costs
Denys Yemshanov, Natural Resources Canada, Canadian Forest
Service, Great Lakes Forestry Cente, Sault Ste. Marie, ON,
P6A2E5, Canada,
Robert G Haight, Frank H. Koch, Robert Venette, Kala Studens,
Ronald Fournier, Jean J Turgeon
We present a scenario-based model that incorporates uncertainty about the
spread of an invasive pest and optimizes the deployment of survey and control
measures to eradicate the outbreak. The model accounts for program success
aspirations and controls the risk of high program costs. We apply the model to
allocate surveys outside the quarantine area established following the discovery of
Asian longhorned beetle in the Greater Toronto Area, Canada. Our approach is
generalizable and helps support decisions on surveys and control of invasive pests
when knowledge about a pest’s spread is uncertain.
SB11
104A-MCC
Clusters, Routes and Flows in Network Systems
Sponsored: Optimization, Network Optimization
Sponsored Session
Chair: Foad Mahdavi Pajouh, University of Massachusetts Boston,
100 Morrissey Boulevard, Boston, MA, 02125, United States,
1 - Extreme-point Search Heuristics For Generalized Interval-flow
Network Problems
Angelika Leskovskaya, Southern Methodist University, Dallas, TX,
United States, , Richard Barr
Generalized interval-flow networks are a new extension of the classic generalized
network formulation that adds a conditional lower bound constraint on the arcs.
An interval-pivoting heuristic that exploits the quasi-tree-forest basis structure to
explore extreme points is developed and computational testing is presented.
2 - Detecting Central Clusters In Networks
Maciej Rysz, NRC, , Foad Mahdavi Pajouh
We propose a solution algorithm for identifying the most central clusters in
graphs and examine its effectiveness when the centrality measure is defined by
betweenness and the clusters represent cliques. Numerical experiments
demonstrating the computational performance of the proposed method are
conducted and compared with results obtained from solving an equivalent mixed
integer programming representation.
3 - An Integrated Assignment Routing Network Representation For
Solving The Multi Vehicle Routing Problem With Pickup And
Delivery With Time Windows
Monireh Mahmoudi, Arizona State University, Tempe, AZ, 85283,
United States, , Chen Junhua,
Xuesong Zhou
Generally, in the most commonly used exact approaches for solving the m-
VRPPDTW, i.e., column generation and branch-and-cut, generating additional
columns and cuts is an exhausting and time-consuming task. In this research, we
intend to reach optimality for local clusters derived from a reasonably large set of
passengers on real world transportation networks. In our proposed multi-vehicle
state-space-time network, in order to keep only the non-dominated paths, we
introduce the assignment-based hyper paths which embed passengers’ cumulative
service states. In addition, by the aid of our passengers’ cumulative service
patterns, we are able to take control of the symmetry issue.
SB12
104B-MCC
Approximation Algorithms in Networks
and Scheduling
Sponsored: Optimization, Integer and Discrete Optimization
Sponsored Session
Chair: Viswanath Nagarajan, University of Michigan, 1205 Beal Ave,
Ann Arbor, MI, 48105, United States,
1 - Approximating Min-cost Chain-constrained Spanning Trees:
A Reduction From Weighted To Unweighted Problems
Chaitanya Swamy, Combinatorics & Optimization, University of
Waterloo, 200 University Avenue West, Waterloo, ON, Canada,
Andre Linhares
We consider the problem of finding a min-cost spanning tree satisfying degree
bounds for node-sets that form a chain. We give the first approximation algorithm
for this problem that approximates both the cost and degree bounds by a constant
factor. Our algorithm is based on a novel use of Lagrangian duality to simplify the
cost structure of the underlying problem to obtain a decomposition into uniform-
cost subproblems, and then using a known algorithm for the unweighted
problem. We show that this Lagrangian-relaxation based idea is in fact applicable
more generally and, for any cost-minimization problem with packing side-
constraints, yields a reduction from the weighted to the unweighted problem.
2 - K-trails: Recognition, Complexity, And Approximations
Mohit Singh, Microsoft Research,
Degree-constrained spanning hierarchies, also called k-trail, have been introduced
to model network routing problems. Formally, they describe graphs that are
homomorphic images of connected graphs of degree at most k. In this work, we
show that computational aspects of k-trails can be analyzed using techniques
from algorithmic matroid theory. Exploiting this connection, we resolve several
open questions about k-trails raised by Molnar, Newman, and Sebo. The problems
include the recognition of a k-trail and approximating the minimum weight k-
trail in a graph.
3 - Stabilizing Unstable Graphs Through Minimum Modification
Karthik Chandrasekaran, UIUC,
An undirected graph G is stable if the max-fractional-matching LP (with degree
and non-negativity constraints) has no integrality gap. Motivated by applications
in cooperative game theory, we consider the optimization problem of achieving
stability by modifying the graph to the smallest possible extent. We consider two
modifications: min edge-deletion and min edge-weight-addition. We show that
both these problems are NP-hard and develop approximation algorithms in
certain families of graphs.
4 - Adaptive Submodular Ranking
Fatemeh Navidi, University of Michigan,
We study a general adaptive ranking problem where we need to perform a
sequence of actions on a random user, drawn from a known distribution, so as to
satisfy the user as soon as possible. The user is said to be satisfied when its
individual submodular function value goes above some threshold. We obtain a
logarithmic factor approximation algorithm for this problem, which is the best
possible. The adaptive ranking problem has many applications in active learning
and ranking: it generalizes previously-studied problems such as optimal decision
trees, equivalence class determination, decision region determination and
submodular cover, for which our result matches the best known approximation
ratio.
SB11