2016 INFORMS Annual Meeting Program

188 / 561

INFORMS Nashville – 2016
188
MC18
106A-MCC
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,
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,
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, 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
some basic properties of k-CG cuts for the case k ≥ 2.
3 - Extended Formulations For Vertex Cover
Austin Buchanan, Oklahoma State University,
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,
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,
1 - A Backward Sampling Framework For Interdiction Problems
With Fortification
Cole Smith, Clemson University, 110 Freeman Hall, Clemson, SC,
29634, United States, , 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, , 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
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,
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, 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.
MC20
106C-MCC
Systemic Risk, Policies, and Data Needs
Invited: Tutorial
Invited Session
Chair: Agostino Capponi, Columbia University, 500 West 120th street,
New York, NY, 10027, United States,
1 - Systemic Risk, Policies, And Data Needs
Agostino Capponi, Columbia University, 500 West 120th Street,
New York, NY, 10027, United States,
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,
1 - On The Application Of Big Data To Microbial Risk Assessment
Mark Walderhaug, FDA/CBER/OBE,
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.
MC18