Informs Annual Meeting 2017

SA71

INFORMS Houston – 2017

SA71

2 - Solution Methods for the Interdependent Network Flow Problem Negin Enayaty Ahangar, Industrial Engineering, University of Arkansas, nenayaty@email.uark.edu, Kelly Sullivan, Sarah G. Nurre We formulate a multi-layered network flow problem in which the flow of each layer is dependent on the flow of other layers. The formulation can be considered as an extension of the minimum cost flow problem to a multi-layered network. This problem has applications in identifying and mitigating vulnerabilities in interdependent infrastructure systems. We identify valid inequalities to tighten the model’s LP relaxation. We propose a solution methods using these valid inequalities to solve this NP-Hard problem. Computational results are presented to compare the proposed solution method with the traditional branch and bound method. 3 - On Routing Unmanned Aerial Vehicles for Surveillance and Reconnaissance Activities Cai Gao, University at Buffalo, Bell 316, University at Buffalo, Buffalo, NY, 14260, United States, caigao@buffalo.edu, Jose Luis Walteros, Chase Murray We tackle a variation of the close-enough traveling salesman problem in which the salesman is accounted of visiting a node if he traverses a pre-calculated optimal distance through each circular area surrounding the node. This variation arises in the context of unmanned aerial vehicle routing, where a vehicle must cross an area collecting information form a set of targets, while minimizing the detection risks. We consider two approaches for modeling the tradeoff between the amount of collected information and the observed risk and test them by solving a collection of instances adapted from the literature. 4 - An Augmenting Flow Algorithm for a Class of Node-capacitated Maximum Flow Problems Robert Mark Curry, Clemson University, 111 Woodside Lane, Central, SC, 29630, United States, rmcurry@g.clemson.edu, Cole Smith We consider a class of maximum flow problems having node- and arc-capacity constraints, in which each unit of flow on arc (i,j) consumes a non-negative amount of capacity at node i. Rather than solving a linear program for these problems, we present an augmenting flow algorithm. In this algorithm, we augment flows along a path having positive residual capacities among all arcs and nodes along the path. When no such paths exist, we find and augment flow along flow-cycles that increase the residual capacity at an incapacitated node. We prove the optimality and computational complexity of our algorithm and apply it to solve various problems in wireless sensor network settings. 372B Time-Expanded Models and Integer Programming Sponsored: Computing Sponsored Session Chair: Natashia Boland, Georgia Institute of Technology, Atlanta, GA, 30332, United States, natashia.boland@gmail.com 1 - Pickup and Delivery with Synchronized Transfers Monireh Mahmoudi, Arizona State University, Tempe, AZ, United States, mmahmou2@asu.edu, Xuesong Zhou In this paper, we consider complex assignment-routing constraints corresponding to the pickup and delivery problem with time windows and synchronized transfers by constructing multi-dimensional networks. More specifically, we introduce a multi-vehicle state-space-time network in which only non-dominated assignment-based hyper paths are examined. Then, we reach optimality for local clusters derived from a large set of passengers on real-world transportation networks. Extensive experiments over the standard instances and real-world data set show the solution optimality, as well as computational efficiency of our developed algorithm. 2 - Solving Stochastic Scheduled Service Network Design Problems Mike Hewitt, Loyola University Chicago, 370 Grandview Ave, Glen Ellyn, IL, 60137, United States, mhewitt3@luc.edu Consolidation carriers transport shipments that are small relative to trailer capacity. To be cost-effective, a carrier must consolidate shipments, which requires coordinating shipment paths in both space and time. However, they often must determine these shipment paths before all information (e.g. size, times available and due) regarding a shipment is known. In this talk, we present an extension of an iterative refinement algorithm designed to solve Scheduled Service Network Design Problems to stochastic variants. SA73

371F Black-box or Simulation Optimization Sponsored: Optimization, Global Optimization Sponsored Session Chair: Zelda B. Zabinsky, University of Washington, Seattle, WA, 98195-2650, United States, zelda@u.washington.edu 1 - Simulation Optimization of Risk Measures with Adaptive Risk Levels Enlu Zhou, Georgia Institute of Technology, 755 Ferst Drive NW, Atlanta, GA, 30332-0205, United States, enlu.zhou@isye.gatech.edu, Helin Zhu, Joshua Hale Optimizing risk measures such as Value-at-Risk (VaR) and Conditional Value-at- Risk (CVaR) of a general loss distribution is usually difficult, because 1) the loss function might lack structural properties such as convexity or differentiability since it is often generated via black-box simulation of a stochastic system; 2) evaluation of risk measures often requires rare-event simulation, which is computationally expensive. We extend the recently proposed gradient-based adaptive stochastic search (GASS) to the optimization of risk measures VaR and CVaR, and incorporate an adaptive updating scheme on the risk level. 2 - Trust Based Optimization with Adaptive Restart: A Family of Global Optimization Algorithms The field of simulation optimization has seen many algorithms proposed for local optimization drawing upon locally convergent search methods, and numerous global optimization algorithms with differing strategies to achieve convergence. Globally we look into meta-model based algorithms that stochastically drive global search through an optimal sampling criteria evaluated over a predicted response and its uncertainty. We propose Trust Region Based Optimization with Adaptive Restarts (TBOAR), a family of algorithms that dynamically restarts a trust region based local search method via an optimal sampling criteria derived upon a meta-model based global search approach. 3 - Martingale Search Algorithms for Simulation Optimization Seksan Kiatsupaibul, Chulalongkorn University, 65 Soi Sukhumvit 7, Bangkok, 10110, Thailand, seksan@cbs.chula.ac.th, Robert L. Smith, Zelda B. Zabinsky We propose a class of adaptive random search algorithms for simulation optimization that generalizes a number of algorithms in the literature. In the course of the algorithm, design points are sequentially sampled from the design space, according to an adaptive sampling probability function. Objective function values are estimated via shrinking balls, which satisfies a martingale property in a continuous domain. We extend the martingale property to discrete domains, noting that we only make a single observation for each sample point in each iteration, although later returns to the same point will accumulate a collection of observations for the same design point. 372A Emerging Applications in Network Optimization Sponsored: Optimization, Network Optimization Sponsored Session Chair: Robert Mark Curry, Clemson University, Central, SC, 29630, United States, rmcurry@g.clemson.edu 1 - A Centrality Study of Protein-protein Interaction Networks One of the main objectives of Systems biology is to reveal fundamental, architectural principles that provide us with better insight on the underlying structure and functionality at the cellular level. In this talk, we present the state- of-the-art of using centrality indices to analyze and interpret protein-protein interaction networks (PPINs). We then proceed to discuss a series of novel group centrality metrics and their implications for PPINs. Of particular interest to us is a membership centrality index, that builds upon standard centrality metrics. Our results showcase that group centrality enables us with an efficient and effective way to detecting essentiality in the proteome. Logan Michael Mathesen, Arizona State University, 699 S. Mill Ave, Tempe, AZ, 85281, United States, lmathese@asu.edu, Giulia Pedrielli SA72 Saeid Rasti, North Dakota State University, Fargo, ND, United States, saeid.rasti@ndsu.edu, Chrysafis Vogiatzis

28