Informs Annual Meeting 2017

MA75

INFORMS Houston – 2017

MA75

can can play to operationalize MILP postopimality, since the required data can be compiled more concisely and then efficiently retrieved for different queries. 2 - A Binary Decision Diagram Based Algorithm for Solving a Class of Integer Two-stage Stochastic Programs Leonardo Lozano, Clemson University, 423 Lindsay Road, Apt 104, Clemson, SC, 29631, United States, llozano@g.clemson.edu We consider a class of two-stage stochastic integer programming problems with binary variables appearing in both stages and a set-covering structure in the second stage. Our approach uncovers strong dual formulations to the second- stage problems by transforming them into dynamic programming (DP) problems parameterized by first-stage variables. These DPs can be formed by use of binary decision diagrams (BDDs), which then yield traditional Benders inequalities. Moreover, we limit the size of the resulting BDDs using concepts related to the minimization of branchwidth on hypergraphs. We demonstrate the efficacy of our approach on a set of stochastic vertex cover problems. 3 - Novel Dynamic Programming Techniques for Discrete Multiobjective Optimization Andre Augusto Cire, University of Toronto-Scarborough, Department of Management, UTSC, 1265 Military Trail, Toronto, ON, M1C-1A4, Canada, acire@utsc.utoronto.ca, David Bergman, Merve Bodur, Carlos Cardonha In this talk we present a novel dynamic programming (DP) methodology for addressing discrete multiobjective optimization problems. Our technique applies typical decision-diagram operations to remove dominated solutions from the state-transition graph of a DP model, while exploiting its underlying recursive structure to derive more efficient labeling techniques. We apply this concept to enumerate the pareto frontier in multiobjective variants of the knapsack, set covering, and set partitioning problems, exhibiting orders of magnitude improvements over state-of-the-art general-purpose multiobjective optimization algorithms. 4 - An MDD-based Lagrangian Approach to the One-to-one Multi-commodity Pickup-and-delivery TSP Margarita Paz Castro, University of Toronto, 5 King’s College Road, Toronto, ON, Canada, mpcastro@mie.utoronto.ca, Andre Augusto Cire, Chris Beck We address the one-to-one multi-commodity pickup and delivery traveling salesman problem (mPDTSP), a variant of the TSP that includes the delivery of a fixed set of commodities by a capacitated vehicle. We propose an approach that uses a discrete relaxation based on Multivalued Decision Diagrams (MDDs) to better represent the combinatorial structure of the problem. We enhance our relaxation by using the MDDs as a subproblem of a Lagrangian relaxation technique, leading to significant improvements both in bound quality and run time performance. Experimental results show that our approach outperforms state-of-the-art methodologies, closing 27 open instances from the literature. 372F Joint Session OPT/Practice: Recent Progress in Optimization Software I Sponsored: Optimization, Computational Optimization and Software Sponsored Session Chair: Hans Mittelmann, Arizona State University, Tempe, AZ, 85287- 1804, United States, mittelmann@asu.edu 1 - Performance Improvements and New Features in the Gurobi Optimizer Robert E. Bixby, CSO, Gurobi Optimization, Inc., 3733-1 Westheimer Road, Box 1001, Houston, TX, 77027, United States, bixby@gurobi.com This talk will cover the latest developments in the Gurobi Optimizer, especially performance improvements on MIP and LP, such as new and improved cutting planes, presolve reductions, heuristics and symmetry handling. 2 - Recent Improvements in IBM ILOG CPLEX Optimizer Andrea Tramontani, IBM.Italy, Via Martin Luther King, 38/2, Bologna, 40132, Italy, andrea.tramontani@it.ibm.com This talk will cover the latest developments in the CPLEX Optimizer. We will present some of the new features and algorithmic techniques recently added to CPLEX, and we will give benchmark results to assess the performance improvements achieved in the latest CPLEX version. MA77

372D Algorithms for Structured Optimization Problems II Sponsored: Optimization, Nonlinear Programming Sponsored Session Chair: Shiqian Ma, Chinese University of Hong Kong, Shatin, Hong Kong, sqma@se.cuhk.edu.hk Co-Chair: Yunan Zhou, University of Southern California, 2707 Portland Street, Apt 111, Los Angeles, CA, 90007, United States, yunanzho@usc.edu 1 - On the Pervasiveness of Difference-convexity in Optimization and Statistics Maher Nouiehed, University of Southern California, Los Angeles, CA, United States, nouiehed@usc.edu, Jong-Shi Pang, Meisam Razaviyayn This paper establishes the dc property of many well-known functions that appear in diverse engineering and statistical problems. Motivated by a quadratic programming (QP) based recourse function, we show that the (optimal) value function of a copositive QP is dc on the domain of finiteness of the program when the objective function’s quadratic term matrix and the constraint matrix are fixed. We prove this using a dc decomposition of a piecewise LC1 function (function with Lipschitz gradient). Moreover, we show that many composite statistical functions in risk analysis, including expectation/value-at-risk (VaR)/conditional value-at-risk (CVaR)-based random deviation functionals, are all dc. 2 - Proximal Quasi Newton Methods for Convex Optimization Hiva Ghanbari, PhD Candidate, Lehigh University, Bethlehem, PA, 18015, United States, hig213@lehigh.edu, Katya Scheinberg In this work, we analyze the global convergence rate of proximal quasi-Newton algorithm for composite optimization problems, both in the exact and inexact setting, in the case when the objective function is strongly convex. We also investigate a practical variant of this method by establishing a simple stopping criterion for the subproblem optimization. Furthermore, we consider an accelerated variant, to the proximal quasi-Newton algorithm. 3 - On the Resolution of L0-minimization Problems via Alternating Lagrangian Schemes We consider minimization of an objective function that contains l0-norm over a polyhedral set. This problem can be equivalently formulated as a mathematical program with complementarity constraints (MPCC). We prove that weak constraint qualifications hold at feasible points of MPCC, and KKT conditions are sufficient under suitable assumptions. The smooth MPCC formulation are resolved via an ADMM scheme and an augmented Lagrangian scheme. Despite the overall nonconvexity, each ADMM subproblem can be solved efficiently recognizing a hidden convexity property. Moreover, the limit point of both schemes satisfy KKT conditions. Preliminary numerics indicate that these approaches are promising. 4 - Stochastic Game with Chance Constraints: Lagrange Method Yunan Zhou, University of Southern California, Los Angeles, CA, 90007, United States, yunanzho@usc.edu In this paper, we study one algorithm for solving a non-cooperative game with expected value function in the constraints via a Lagrange formulation as a min- max game. The algorithm consists of 2 iterative loops. In the outer loop, an approximal point method is applied. And in the inner loop, the Lagrange method is used to relax constraints and then using sample average approximation method, we solve the problem iteratively. The convergence results of both loops are established in almost surely sense. 372E Decision Diagrams for Optimization Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Thiago Serra, Carnegie Mellon University, Pittsburgh, PA, United States, tserra@cmu.edu 1 - Postoptimality of Mixed-integer Programs with Decision Diagrams Thiago Serra, Carnegie Mellon University, 527-1/2 Gettysburg Street, Pittsburgh, PA, 15206, United States, tserra@cmu.edu, John Hooker We consider what-if analyses on the set of near-optimal solutions of a mixed- integer linear program. For example, to determine the objective function impact of changing a variable or to find the combinations of assignments that define near-optimal solutions. In particular, we look at the role that decision diagrams Yue Xie, Pennsylvania State University, 445 Waupelani Dr, Philadelphia, PA, 16801, United States, yux111@psu.edu MA76

160