2016 INFORMS Annual Meeting Program

TD13

INFORMS Nashville – 2016

TD12 104B-MCC New Results on Polyhedral Relaxations Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Akshay Gupte, Clemson University, Clemson, SC, United States, agupte@clemson.edu 1 - Approximation Guarantees Of Closures Joseph Paat, Johns Hopkins University, jpaat1@jhu.edu Intersection cuts for Gomory’s corner polyhedron can be generated using lattice- free sets. While the intersection of all of these cuts reproduces the corner polyhedron, a question of interest is how well does a subfamily of intersection cuts approximate the corner polyhedron. We examine this question and develop conditions for approximation based on the number of facets of the underlying lattice-free sets. This work was done in collaboration with Gennadiy Averkov from the University of Magdeburg in Germany, and Amitabh Basu from Johns Hopkins University in the USA. 2 - Some Lexicographic Perspectives On Valid Inequalities Michael Eldredge, Clemson University, michaelgeldredge@gmail.com, Akshay Gupte If B is a box in n-dimensional space, then the convex hull of integer points that are lexicographically between two given points is describable with 4n linear constraints. In this presentation we analyze a process that exploits this representation to define disjunctions and split cuts in integer programming problems, including presenting complexity results for determining the feasibility of lexicographically defined sets. 3 - An Efficient Algorithm For Trivial Lifting In Two Dimensions Alinson Xavier, University of Waterloo, Waterloo, ON, Canada, axavier@uwaterloo.ca, Ricardo Fukasawa, Laurent Poirrier When generating cuts for MIPs from multiple rows of the simplex tableau, the usual approach has been to relax the integrality of the non-basic variables, compute an intersection cut, then strengthen the cut coefficients corresponding to integral non-basic variables using the so-called trivial lifting procedure. Although of polynomial-time complexity in theory, this lifting procedure can be computationally costly in practice. For two-row relaxations, we present an algorithm that computes trivial lifting coefficients in constant time, for arbitrary maximal lattice-free sets. Computational experiments confirm that the algorithm works well in practice. We discuss possible generalizations. 4 - On MIP Relaxations For Nonlinear Programs Taotao He, Purdue University, Rawls Hall, 100 S Grant Street, West Lafayette, IN, 47907-2076, United States, he135@purdue.edu, Mohit Tawarmalani In this talk, we propose new recursive relaxation techniques for factorable programs. We consider the graph of product on non-negative convex functions and show that tighter relaxations than the McCormick scheme can be developed in a variety of ways. We use these schemes in conjunction with disjunctive programming to develop a hierarchy of MIP relaxations whose optimal value converges asymptotically to that of the nonlinear program. We provide preliminary computations to demonstrate the efficacy of our scheme. TD13 104C-MCC Software and Methodologies for (Nonlinear) Integer Programming Sponsored: Optimization, Computational Optimization and Software Sponsored Session Chair: Alexandra M Newman, Colorado School of Mines, Golden, CO, United States, anewman@mines.edu 1 - Software For Nonlinearly Constrained Optimization Sven Leyffer, Argonne National Laboratory, leyffer@anl.gov We survey different methodologies for solving general nonlinearly constrained optimization problems, including interior-point, augmented Lagrangian, and active-set methods. We discuss linear algebra requirements of these different techniques; present different globalization strategies; and comment on their relative performance for solving large-scale optimization problems. Time permitting we will present preliminary results with a new solver library that we are developing.

2 - Supply Chain Design As A Mechanism To Introduce Biofuel Feedstock Adoption In Africa Liang Lu, UC Berkeley, Berkeley, CA, United States, lld2x1515@berkeley.edu, Wei Qi, Zuo-Jun Max Shen, David Zilberman Many biofuel projects in Africa are not sufficiently developed to benefit smallholders. We propose models of capacity planning and dynamic feedstock sourcing design for a biorefinary. We show that refineries have to reach a critical capacity to justify outsourcing. The role of smallholders’ learning rate/project length/credit availability/government subsidy are discussed. 3 - Designing A Reliable And Congested Multi-modal Facility Location Problem For Bio-fuel Supply Chain Network Sushil Raj Poudel, Mississippi State University, Dept of Industrial & Systems Engineerring, PO Box 9542, Starkville, MS, 39762, United States, srp224@msstate.edu, MD Abdul Quddus, Mohammad Marufuzzaman, Sudipta Chowdhury, Brian Smith, Linkan Bian This study presents a mathematical model that designs a reliable multi-modal transportation network for a bio-fuel supply chain system. The proposed model investigates the effect of different levels of congestion and disruption on locating multi-modal facilities and bio-refineries. The nested decomposition algorithm we propose combine Constraint Generation (CG) and Rolling Horizon (RH) to solve this NP-hard problem. Results obtained from the experiments revealed that the effect of congestion reduces the total number of multi-modal facilities and the consideration of disruption probability move away the facilities from coastal areas while increasing the total unit cost of bio-fuel. TD11 104A-MCC Quality-Guaranteed Network Design: Interdiction, Routing, and Resource Allocation Sponsored: Optimization, Network Optimization Sponsored Session Chair: Tachun Lin, Assistant Professor, Bradley University, 1501 W Bradley Ave, Bradley Hall 171, Peoria, IL, 61625, United States, djlin@bradley.edu 1 - Risk-averse Bi-level Stochastic Network Interdiction Model For Cyber-security Tanveer Hossain Bhuiyan, Mississippi State University, P.O Box 9542, 260 McCain Hall,, Mississippi State University, Starkville, MS, 39762, United States, tb2038@msstate.edu, Apurba K Nandi, Hugh Medal We propose a bi-level stochastic network interdiction model to enable a risk- averse and resource constrained cyber network defender to optimally deploy security countermeasures. The model minimizes both the overall expected maximum loss and the expected loss from worst cyber-attacks while capturing the interaction between the defender and the attacker. The budget of an attacker in our model is uncertain. In the presence of uncertain attack scenarios, this risk aversion approach provides a more robust interdiction plan as compared to the risk-neutral approach. We develop parallelizable exact and heuristic algorithms to solve the model. 2 - Revisiting Integrated Fleeting And Routing Design For International Flight Management Zhili Zhou, United Airlines, zhili.zhou@united.com We study the integrated fleeting and routing problem for international flight management, which requires maximally preserve the consistency of fleet and flight leg assignment. We analyze the historical patterns of fleet routes and develop approximation algorithms for fleet routing through splitting and adding with historical patterns as base. We further integrate the routing model with fleeting model. Computational results demonstrate that the solution approaches achieves assignment consistency and CAPEX maximization. 3 - Network Function Placement: A Game-theoretic Approach Tachun Lin, Bradley University, djlin@bradley.edu Network function virtualization decouples network functions from proprietary networking hardware and enables adaptive services to end-user requests. We study a network virtualization scheme and propose an integrated design for network function instance allocation and end-to-end demand realization sharing the same physical substrate network. We first propose an MILP formulation to find the optimal solution, and then present a two-player pure-strategy game which captures the competition on physical resources between network function instance allocation and routing. We then design an algorithm based on iterative weakly dominated elimination in Game Theory to solve this problem.

337