Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

MD08

3 - An Empirical Investigation of Network Polarization Celso C. Ribeiro, Universidade Federal Fluminense, Rua Capistrano de Abreu 28, Apartment 702, Rio de Janeiro, 22271-000, Brazil, Ruben Interian New tools for evaluating the polarization of a network are presented. We depart from the definition of a new measure of node homophily and consider the homophily distribution over the nodes as an indicator of the strength of polarization. Next, to address the polarization of the network as a whole, a probabilistic approach is developed, providing a more insightful understanding of the status of the network. The usefulness of the approach is illustrated on real-life networks. Two graph optimization problems are formulated and explored to deal with the reduction of polarization: (1) the maximum-cardinality homophily reduction problem and (2) the minimum-cardinality balanced edge addition problem. 4 - Supervalid Inequalities for Network Interdiction Problems We focus on attacker-defender network interdiction problems in which: 1) the objective minimizes the attacker’s cost of achieving a fixed disruption level over the defender’s problem; 2) the defender’s problem is to select an optimal graph structure (e.g., a shortest path, a spanning tree) over the residual graph; 3) the attacker strategies are defined over the same ground set of the graph structures. e.g., if the structures are defined over the edges, the attacker also interdicts edges. We develop a cut-generating framework that produces a general class of supervalid inequalities that remove non-trivial suboptimal solutions. We show how to addapt our framwework to tackle a wide variety of problems. 5 - Routing and Wavelength Assignment for All-optical Networks: A Defender-attacker-operator Game Mehdi Hemmati, New Mexico State University, Las Cruces, NM, 88011, United States, Cole Smith All-optical Networks (AONs) form the foundation of Internet backbone. They transmit the data over light rays, which require dedicated wavelengths. Hence, the routing problem in AONs turns into the so-called Routing and Wavelength Assignment (RWA) problem. We discuss an extension of the RWA problem to study the resilience of AONs in the presence of intentional disruptions. We propose a multi-level integer program and investigate the solution techniques by studying the solution space of the related optimization problem. 6 - Adaptivity in Network Interdiction Bastian Bahamondes, Universidad de Chile, Santiago, Chile, Jose Correa, Jannik Matuschke, Gianpaolo Oriolo We study a network security game arising in the interdiction of fare evasion or smuggling. A defender places a security checkpoint in the network according to a chosen probability distribution over the links. An intruder, knowing this distribution, wants to travel from her initial location to a target node. For every traversed link she incurs a cost equal to its transit time, and if she encounters the checkpoint, she has to pay a fine. The intruder may adapt her path online, exploiting additional knowledge gained along the way. We study the complexity of computing optimal strategies for the intruder and defender and the worst-case ratio of the intruder’s best adaptive to her best non-adaptive strategies. n MD08 North Bldg 124A Joint Session OPT/Practice Curated: Integer Programming for Network Optimization and Applications Sponsored: Optimization/Network Optimization Sponsored Session Chair: Ou Sun, University of Arizona, Tucson, AZ, 85719, United States Co-Chair: Neng Fan, University of Arizona, Tucson, AZ, 85721, United States 1 - Algorithms and Complexity Results for Routing Trains through a Railyard Kelly Sullivan, University of Arkansas, 4207 Bell Engineering Center, 1 University of Arkansas, Fayetteville, AR, 72701, United States, Negin Enayaty Ahangar We consider the problem of identifying a shortest route for a locomotive pulling a cut of cars through a railyard network in which nodes correspond to switches and edges correspond to tracks. As compared to a traditional shortest path problem, this problem is challenging because the route must accommodate, subject to the geometry of the yard tracks, the length of the cut of cars plus the length of the locomotive at any time. We model this problem as an integer program, prove its NP-hardness, and propose a solution approach that is polynomial for an important special case. Ningji Wei, PhD Candidate, University at Buffalo, SUNY, North Tonawanda, NY, United States, Jose Luis Walteros

2 - Benders Cut-and-solve: A New Versatile Tool for Network Optimization Carlos Armando Zetina, Concordia University, CORS/INFORMS Montreal Operations Research Stu, 1455 de Maisonneuve Boulevard W, Montreal, QC, H3G 1M8, Canada, Ivan Contreras, Jean-Francois Cordeau Cut-and-solve has been used to solve the TSP and facility location to optimality. This method can be thought of as a generalized local branching in which at each level of the enumeration tree only two child nodes exist, one corresponding to a smaller “sparse’’ problem and the other as its complement known as the “dense’’ problem. We propose the use of Benders-based branch-and-cut as the black box MIP solver for “sparse” problems. Two important advantages of this are the reduced problem size and the re-usability of the Benders cuts generated in previous iterations. We present promising computational results for a naive implementation used to solve the fixed-charge multicommodity network design problem. 3 - Minimum Cost Vertex Blocker Clique Problem Farzaneh Nasirian, University of Massachusetts-Boston, 100 William T. Morrissey Blvd, Boston, MA, 02125, United States, Foad Mahdavi Pajouh, Josephine Namayanja This talk addresses the minimum cost vertex blocker clique problem (CVCP) in which we are interested in detecting a subset of vertices in a graph with a minimum blocking cost whose removal bounds the weight of any weighted clique in the remaining graph by a given r>0. We propose new linear 0-1 programming formulations with the exponential number of constraints and a new set of facets for the CVCP polytope. We also develop the first combinatorial branch-and-bound algorithm to solve this problem. The computational performance of these exact algorithms is studied on a test-bed of randomly-generated and real-life graphs. 4 - Manufacturing Processes with Renewable Energy Integration and Demand Response Jose Luis Ruiz Duarte, University of Arizona, 1127 E. James E. Rogers Way, Tucson, AZ, 85721, United States, Neng Fan International efforts for CO2 reduction require the engagement of industry sector, as a major energy consumer in the world. The integration of renewable energy sources (RES) into manufacturing processes is an alternative. In this work, a mathematical programming model is developed to obtain the optimal production schedule considering consecutive processes, integration of both onsite and grid RES, onsite energy storage systems, and demand response policies. Robust formulation approach is used to obtain optimal operations under the worst-case scenario for RES generation. A solution algorithm is developed to solve this formulation and is validated by numerical experiments 5 - A Stochastic Mixed Integer Programming for GIS-based Biorefinery Facility Location Problem Ou Sun, University of Arizona, 827 E. Drachman Street, Tucson, AZ, 85719, United States, Neng Fan A typical biomass supply chain consists of the following five components: harvesting and collection, storage, pretreatment, transportation, and conversion. Facility location problem is embedded in and vital to both pretreatment, and conversion processes. Geographic information system (GIS) is widely used to decide the facility locations with consideration of different related factors. Due to the special characteristics of biomass, the harvest yield is uncertain, which leads to the uncertainties through the whole supply chain. We take uncertainties into consideration and formulate a stochastic mixed integer programming by utilizing GIS tools for biorefinery facility location problem. n MD09 North Bldg 124B Methods for Large Scale Nonlinear and Stochastic Optimization II Sponsored: Optimization/Nonlinear Programming Sponsored Session Chair: Albert Solomon Berahas, Evanston, IL, 60208, United States Co-Chair: Francisco Jara-Moroni, Northwestern University, Evanston, IL, 60208, United States 1 - A Stochastic Line Search Method with Convergence Rate Analysis For deterministic optimization, line-search methods augment algorithms by providing stability and improved efficiency. We adapt a classical backtracking Armijo line-search to the stochastic optimization setting. While traditional line- search relies on exact computations of the gradient and values of the objective function, this method assumes that these values are available up to some dynamically adjusted accuracy which holds with some sufficiently large, but fixed, probability. We show the expected number of iterations to reach a near stationary point matches the worst-case efficiency of typical first-order methods, for nonconvex convex and strongly convex objectives Katya Scheinberg, Lehigh University, 200 W. Packer Ave, Bethlehem, PA, 18015, United States, Courtney Paquette

216