Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

SD06

3 - First-order Methods for Non-convex Non-smoothminimaxoptimization

4 - GOSSIP: Decomposition Software for the Global Optimization of Nonconvex Two-Stage Stochastic Mixed-Integer Nonlinear Programs Rohit Kannan, University of Wisconsin-Madison, Paul I. Barton Despite rapid advances in decomposition techniques for solving two-stage stochastic MINLPs, there is, to the best of our knowledge, no publicly available software framework that implements these techniques. Motivated by the increasing interest in solving this rich class of problems, we present our decomposition framework named GOSSIP. GOSSIP includes implementations of nonconvex generalized Benders decomposition, Lagrangian relaxation, and a modified Lagrangian relaxation algorithm along with subroutines for detecting special structure and bounds tightening. The capabilities of GOSSIP are demonstrated on a library of diverse test instances composed from the literature. n SD07 North Bldg 123 Joint Session OPT/Practice Curated: Network Analytics: Models and Applications Sponsored: Optimization/Network Optimization Sponsored Session Chair: Jose Luis Walteros, University at Buffalo, SUNY, Buffalo, NY, 14260, United States 1 - An Integer Programming Approach for Vertex Connectivity Interdiction Problems Demetrios Papazaharias, University at Buffalo, Buffalo, NY, 14260, United States, Jose Luis Walteros The vertex connectivity interdiction problem entails finding the minimum subset of vertices in an undirected graph whose deletion achieves a desired reduction in the graph’s connectivity. In particular, we aim to reduce the size of the largest component to at most k. In this paper, we introduce a 0-1 linear programming model with an extended formulation and cutting planes to strengthen its LP relaxation. We present computational experiments to compare our results to competing formulations as well as highlight interesting results for graphs containing a special structure. 2 - Distance Between Two Random Events in a Network Ningji Wei, University at Buffalo, SUNY, Buffalo, NY, United States, Jose Luis Walteros, Rajan Batta We are interested in the shortest distance D of two random events in any given connected network where the lengths of edges are not negligible. We found the closed form formula for its expectation, and any order higher moments. Also found its PDF in closed form. In application, we may encounter the situation that one distribution is under our control, so we also found those statistics for the shortest distance conditioning on one of the events. Further, we analyzed the property of there statistics, and also their computational complexity with respect to the size of the network. Finally, we applied our results on some special type networks. 3 - Optimal Corridor Design in Fragmented Landscapes Chao Wang, Arizona State University, Tempe, AZ, United States, Jorge A. Sefair Corridor design is fundamental in conservation planning to mitigate the adverse effects of habitat fragmentation. Current approaches focus on network analysis and landscape features but ignore the likelihood of movement and species mortality. To overcome these challenges, we present a discrete time Markov chain approach that allows us to predict transient and long-term connectivity measures. We also discuss a MIP formulation to find corridors with the highest expected usage to connect a network of fragmented landscapes. We discuss our models using a real case study of human-wildlife conflict. 4 - Studying the Trade-off Between Police Presence and Patrolling in a Road Network Fatemeh Mousapour, University at Buffalo, Buffalo, NY, 14260, United States, Jose Luis Walteros, Rajan Batta Patrolling and adequate coverage are two key factors in police patrolproblems respectively to stop, deter and prevent crimes. Our approach integrates some aspects of the traditional orienteering problem within a patrolling model to examine the trade-off between police presence in specific spots and patrolling through a road network.

Qihang Lin, The University of Iowa, 21 East Market Street, S380, Pappajohn Business Building, Iowa City, IA, 52245, United States In this paper, we consider the minimization of the maximum of finitely many weakly convex functions. Such a formulation has applications in machine learning and robust optimization. We model this problem equivalently as a min- max saddle-point problem. Due to the non-convexity, it is challenging to find a global saddle-point in general. We propose a primal-dual first-order method for this saddle-point problem and analyze the total iteration complexity of our method for finding an epsilon-nearly stationary point. Our method is developed for both stochastic and finite-sum problems. 4 - A Level Set Method for Constrained Stochastic Optimization Negar Soheili, University of Illinois-Chicago, 601 S. Morgan Street, University Hall 2416, Chicago, IL, 60607, United States, Qihang Lin, Selvaprabu Nadarajah Stochastic optimization problems with expectation constraints (SOEC) arise in several operations research and financial engineering applications. Only recently has an efficient stochastic subgradient method been developed for solving a SOEC defined by an objective and a single inequality constraint, where both are defined by expectations of stochastic convex functions. We develop a level-set method to compute near-optimal solutions to a generalization of this SOEC containing multiple inequality constraints, each involving an expectation of a stochastic convex function. We establish convergence guarantees for this method under different convexity assumptions. n SD06 North Bldg 122C Computational Stochastic Programming Sponsored: Optimization/Computational Optimization and Software Sponsored Session Chair: Rohit Kannan, PhD, University of Wisconsin, Madison, WI, United States 1 - Recent Computational Advances in Multistage Stochastic Programs Yongjia Song, Clemson University, 211 Fernow Street, 264 Freeman Hall, Clemson, SC, 29634, United States, Wim van Ackooij, Welington de Oliveira, Murwan Siddig We consider decomposition techniques for multistage stochastic programming. The proposed algorithms combine ideas from finite perturbation of convex programs and level bundle methods to regularize the so-called forward step of these decomposition methods. On the other hand, the backward step of the decomposition methods is accelerated via recent developments in cutting plane approaches. Numerical experiments on a hydrothermal scheduling problem indicate that our algorithms are competitive with the state-of-the-art, e.g., the multistage regularized decomposition and the stochastic dual dynamic programming methods in the literature. 2 - An Improved Branching Approach for Branch-and-bound Applied to Stochastic Mixed-integer Programs Brian Christopher Dandurand, Argonne National Laboratory, Kibaek Kim We present a new branch-and-bound approach for the extended split-variable form of stochastic mixed-integer programs. During the bounding of each node, we assume the generation of: 1) a set of “column” solutions satisfying integrality; and 2) a “consensus” solution satisfying non-anticipativity. Branching is informed by an interweaving of 1) the violations of consensus integrality, and 2) a suitable measure of dispersions of the column solutions around the consensus solution. The measure of dispersion adapts to the changing profile of integrality violation, and the branching scheme only requires branching on first-stage variables. We discuss computational tests on SIPLIB test problems. 3 - A Scalable Global Optimization Algorithm for Stochastic Nonlinear Programs Yankai Cao, University of Wisconsin-Madison, 2009 Engineering Hall, 1415 Engineering Drive, Madison, WI, United States, Victor Zavala We present a reduced-space spatial branch and bound (BB) strategy for two-stage stochastic nonlinear programs. At each node, a lower bound is constructed by relaxing the non-anticipativity constraints and an upper bound is constructed by fixing the first-stage variables. Both lower and upper bounds can be computed by solving individual scenario subproblems. Another key property is that we only need to perform branching on the first-stage variables to guarantee convergence. We present an implementation of the algorithm called SNGO. We perform numerical experiments and compare the computational results against SCIP and demonstrate that the proposed approach achieves significant speedups.

92