2016 INFORMS Annual Meeting Program

MC18

INFORMS Nashville – 2016

MC18 106A-MCC

maximize the physical flow and the objective of the attacker is to minimize this maximum amount. There exist interdependencies between the networks which lead to a network interdiction problem with a discrete inner problem. We reformulate the problem by using duality and obtain a single-level model. We apply this technique to the applications of combating illegal drug trafficking and protecting cyber infrastructures, and present computational results. 3 - Integer Programming Formulations For Minimum Spanning Tree Interdiction Ningji Wei, University at Buffalo, Buffalo, NY, United States, ningjiwe@buffalo.edu, Jose Luis Walteros, Foad Mahdavi Pajouh We solve the problem of removing a set of edges with minimized removal cost in a weighted graph so that the weight of any spanning tree in the remaining graph is bounded below by a value r. We developed several formulations and compare their strength analytically. We also study the convex hull of feasible solutions and identify several facets, as well as other polyhedral properties. Finally we present the computational results for three algorithms. 4 - Assortment Optimization Under Worst-case In-store Consumer Shopping Behavior Saharnaz Mehrani, Arizona State University, Tempe, AZ, United States, smehrani@asu.edu, Jorge A. Sefair We study an assortment problem that incorporates in-store customer response to product unavailability. In this approach, each customer has a list of products to be purchased in a given sequence. If at some point of the sequence a product is not available, the customer either chooses a substitute product or leaves the store. We propose a multi-level optimization approach to find a robust assortment under a worst-case customer’s shopping list and purchasing sequence. Our approach includes a probabilistic model of the customer in-store behavior embedded into an integer program. Invited: Tutorial Invited Session Chair: Agostino Capponi, Columbia University, 500 West 120th street, New York, NY, 10027, United States, ac3827@columbia.edu 1 - Systemic Risk, Policies, And Data Needs Agostino Capponi, Columbia University, 500 West 120th Street, New York, NY, 10027, United States, ac3827@columbia.edu The study of financial system stability is of fundamental importance in modern economies. The failure or distress experienced by systemically important financial institutions can have contagious effects on the rest of the financial system. This may in turn result in deteriorating macroeconomic conditions and price instability, with negative consequences and spillover effects to other sectors of the real economy. This tutorial surveys the different approaches put forward by academic and practitioner literature to systemic risk modeling and measurement. We analyze the relevant economic forces in play, the mechanisms leading systemic instabilities, and discuss the methodologies used in the analysis. We discuss macroprudential, monetary and resolution policies targeting financial stability. We highlight the supervisory authorities of the different financial institutions, as well as barriers to data sharing. MC21 107A-MCC Applications Supporting Clinical and Public Health Decision Making Sponsored: Health Applications Sponsored Session Chair: Hussein Ezzeldin, ORISE, 10903 New Hampshire Ave, Bldg 71 Rm 1009C, Silver Spring, MD, 20993, United States, hussein.ezzeldin@fda.hhs.gov 1 - On The Application Of Big Data To Microbial Risk Assessment Mark Walderhaug, FDA/CBER/OBE, mark.walderhaug@fda.hhs.gov, Steven Anderson “Big Data” is a term that seems to be currently inescapable. New hardware, software, and data sources are transforming the nature and size of risk assessment models. Each component of microbial risk assessment is impacted by big data. Hazard Identification is becoming knowledge discovery. Dose-Response is being refined by both microbial and human variability on the genetic level. Exposure assessment is gaining depth through data made available by the evolving Internet of Things. The use of big data and sophisticated software models creates a highly complex risk characterization that is a challenge to manage, to process, and to meaningfully communicate results to risk managers and to stakeholders. MC20 106C-MCC Systemic Risk, Policies, and Data Needs

Recent Developments in Integer Programming Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Diego A Moran, Universidad Adolfo Ibañez, Diagonal Las Torres 2640, Santiago, 7941169, Chile, damr@vt.edu 1 - An Algorithm To Exploit Diversification And Exploration For Solving Mixed-integer Linear Programs Rodolfo Carvajal, Universidad Adolfo Ibáñez, Viña del Mar, Chile, rodolfo.carvajal@uai.cl, Shabbir Ahmed, George L Nemhauser Mixed-Integer Linear Programming solvers are known to exhibit performance variability. We present an algorithm that takes advantage of this variability by using diversification together with exploration during the tree search. Preliminary computational results are presented. 2 - On Multi-row Chvatal- Gomory Cuts Babak Badri Koohi, PhD Candidate, Virginia Tech, Blacksburg, VA, United States, babakbk@vt.edu, Diego A Moran In recent years, cutting planes obtained from multi-row relaxations of polyhedra have been widely studied in the integer programming community, both from a theoretical and computational point of view. In this talk, we study k-row Chvatal- Gomory (k-CG) cuts, that are obtained by computing integer hulls of k-row relaxations of a polyhedron. This is a generalization of Chvatal-Gomory (CG) cuts (k=1), a very important class of cuts that is well-understood. Here, we present Austin Buchanan, Oklahoma State University, buchanan@okstate.edu The vertex cover polytopes of graphs do not admit polynomial-size extended formulations. This motivates the search for polyhedral analogues to approximation algorithms and fixed-parameter tractable (FPT) algorithms. In this paper, we take the FPT approach and study the k-vertex cover polytope (the convex hull of vertex covers of size k). Our main result is that there are extended formulations of size O(kn+1.47^k). We also provide FPT extended formulations for solutions of size k to instances of d-hitting set. 4 - Complete Efficient Frontier Of Multidimensional Nonlinear Knapsack Problems With Multiple Objectives Yuji Nakagawa, Kansai University, nakagawa@res.kutc.kansai-u.ac.jp, Yoshiko Hanada, Chanaka Edirisinghe We propose a technique for finding all efficient solutions of multi-objective nonlinear separable discrete optimization problems using a unique enumeration approach, termed the Target Method, based on the surrogate constraint technique. The Target Method is superior to the existing algorithms, in both speed and accuracy, on 0-1 separable discrete problems with a single constraint. Comparative results of the proposed method and metaheuristic are presented. MC19 106B-MCC Multilevel Optimization Models and Applications Sponsored: Computing Sponsored Session Chair: Jorge A Sefair, Arizona State Univerity, 699 S. Mill Ave., BYENG 330, Tempe, AZ, 85281, United States, jorge.sefair@asu.edu 1 - A Backward Sampling Framework For Interdiction Problems With Fortification Cole Smith, Clemson University, 110 Freeman Hall, Clemson, SC, 29634, United States, jcsmith@clemson.edu, Leonardo Lozano We examine three-stage sequential defender-attacker-defender problems that are notoriously difficult to optimize, and almost always require the third-stage (recourse) problem to be convex. We propose an approach in which we allow the recourse problem to take any form. The proposed framework restricts the defender to select a recourse decision from a sample of feasible vectors and iteratively refines the sample to force finite convergence to an optimal solution. We provide computational experiments on different interdiction problems with fortification to demonstrate that our algorithm solves problems involving NP-hard recourse problems within reasonable computational limits. 2 - Interdicting Layered Information And Physical Flow Networks Orkun Baycik, Rensselaer Polytechnic Institute, Troy, NY, United States, baycin@rpi.edu, Thomas Sharkey, Chase Rainwater We study the interdiction of layered networks that involve a physical flow network and an information flow network. The objective of the defender is to some basic properties of k-CG cuts for the case k ≥ 2. 3 - Extended Formulations For Vertex Cover

188