2016 INFORMS Annual Meeting Program

SB11

INFORMS Nashville – 2016

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, viswa@umich.edu 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, cswamy@uwaterloo.ca 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, mohitsinghr@gmail.com 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, karthe@illinois.edu 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, navidi@umich.edu 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.

3 - Optimal Design Of A Nation-wide Surveillance System For Early Detection Of An Invasive Bark Beetle Rebecca Epanchin-Niell, Resources for the Future, Epanchin-Niell@rff.org 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, denys.yemshanov@canada.ca 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, foad.mahdavi@umb.edu 1 - Extreme-point Search Heuristics For Generalized Interval-flow Network Problems Angelika Leskovskaya, Southern Methodist University, Dallas, TX, United States, aleskovs@lyle.smu.edu, 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, mwrysz@ufl.edu, 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, mmahmoudi@asu.edu, 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.

46