Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

SB05

2 - On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization Jeffrey Zhang, Princeton University, 206 Lakeside Road, Princeton, NJ, 08540, United States, Amir Ali Ahmadi We prove that it is strongly NP-Hard to test whether the optimal value of a nonlinear optimization problem is attained for certain degrees of the objective and constraints. Our results along with previously-known ``Frank-Wolfe type’’ theorems settle the complexity for any combination of degrees. We also show that testing for some well-known sufficient conditions for attainment of the optimal value, such as coercivity of the objective function, compactness of the feasible set, and the Archimedean property of a related quadratic module is strongly NP-hard. Finally, we give SDP-based sufficient conditions for attainment of the optimal value, such as a new characterization of coercive polynomials. 3 - Exact Lexicographic Scheduling and Approximate Rescheduling Dimitrios Letsios, Imperial College London, London, United Kingdom, Ruth Misener We consider the fundamental two-stage robust makespan scheduling problem with a planning and a recovery phase. We show that planning using lexicographic optimization imposes optimal substructure that enables more efficient recovery with performance guarantees. We propose a novel lexicographic branch-and- bound method using vectorial bounds to deal with the lack of strong lower bounding techniques in exact lexicographic optimization MILP methods. Numerical analysis using standard commercial approaches substantiates the strength of our methods. 4 - Intersection Disjunctions for Reverse Convex Sets Eli Towle, University of Wisconsin-Madison, Madison, WI, 53705, United States, James Luedtke We present a framework to obtain valid inequalities for a reverse convex set, defined as the set of points in a polyhedron that lie outside a given open convex set. Our contribution is a disjunctive framework that uses basic solutions that lie outside the convex set to generate valid inequalities. We define a two-term disjunction for a reverse convex set. Next, we generalize this analysis to a multi- term disjunction by considering the convex set’s recession directions. We present a polyhedral relaxation for each disjunctive term, allowing the approach to be used to generate disjunctive cuts. Chair: Gary Au, PhD, University of Saskatchewan, SK, Canada 1 - Lift-and-project Lower Bounds for Hypermatching Relaxations Yu Hin (Gary) Au, University of Saskatchewan, 106 Wiggins Road, 239 McLean Hall, Saskatoon, SK, S7N 5E6, Canada, Levent Tuncel, Nathan Lindzey In 1999, Stephen and Tuncel showed that the Lovasz-Schrijver lift-and-project operator with semidefiniteness requires exponential effort to compute the integer hull of the standard linear relaxation of the matching polytope. Herein, we extend their results to b-matching polytope of complete uniform hypergraphs, utilizing some known results in association schemes. 2 - Using Mixed Precision Arithemtic in an Interior Point Method for SDP Brian Borchers, New Mexico Institute of Mining & Technology, Dept of Mathematics Weir Hall, 801 LeRoy Place, Socorro, NM, 87801-4796, United States Interior point methods for semidefinite programming are typically implemented in double precision floating point due to the fact that the Schur complement matrix that must be factored in each iteration becomes ill-conditioned as the iterates approach an optimal solution. Since single precision arithmetic is typically twice as fast as double precision, there are potential performance advantages to usig single precision arithmetic in those parts of the algorithm and during those phases of the algorithm where single precision is sufficient. We describe an implementation of a mixed-precision primal-dual method for SDP and demonstrate its performance on benchmark problems. n SB05 North Bldg 122B Semidefinite Optimization I Sponsored: Optimization/Linear and Conic Optimization Sponsored Session

3 - Two Dimensional Search Interior Point Algorithms for Linear Programming

Fabio T. Vitor, Kansas State University, 2061 Rathbone Hall, 1701B Platt St., Manhattan, KS, 66506, United States, Todd W. Easton Interior point methods optimally solve linear programs by moving between feasible interior solutions. The majority of these algorithms move between solutions following a single direction. This talk presents novel primal and dual two dimensional interior point methods derived from affine and logarithmic barrier directions. These techniques use two potential improving directions to create a two dimensional problem. The optimal solution to this problem enables the algorithms to move to a new and improved feasible interior solution. Computational experiments show an improvement in solution time and iterations of approximately 12% when compared to the traditional one dimensional version. n SB06 North Bldg 122C Computational Optimization Sponsored: Optimization/Computational Optimization and Software Sponsored Session Chair: Julio Cesar Goez, NHH, Department of Business and Management Science, Bergen, 5036, Norway 1 - A Novel Initialization Procedure for the Simplex Algorithm Nikolaos Ploskas, Carnegie Mellon University, 5000 Forbes Avenue, Doherty Hall 3110, Pittsburgh, PA, 15213, United States, Nikolaos Sahinidis, Nikolaos Samaras This paper addresses the computation of a starting basis for the simplex algorithm. We propose six algorithms for constructing an initial basis. We give the initial bases as input to the CPLEX solver and compare the performance of the primal and dual simplex algorithm using the proposed algorithms against CPLEX advanced starting basis and crash procedures. The best algorithm results in 7% and 6% average reduction of the execution time of CPLEX’s primal and dual simplex algorithm, respectively. Taking into account only the hard instances, the proposed algorithm results in 23% and 32% average reduction of the execution time of CPLEX’s primal and dual simplex algorithm, respectively. 2 - Warm-start of Interior Point Methods for Second Order Cone Optimization via Jordan Frames Tamás Terlaky, Endowed Chair Professor, Lehigh University, 200 West Packer Avenue, Bethlehem, PA, 18015, United States, Imre Polik, Sertalp Bilal Cay IPMs are the most popular approaches to solve Second Order Cone Optimization (SOCO) problems. We present a warm-start method for primal-dual IPMs to reduce the number of IPM steps needed to solve SOCO problems that appear in a Branch and Conic Cut (BCC) tree when solving Mixed Integer Second Order Cone Optimization (MISOCO) problems. Our method exploits the optimal Jordan frame of a related subproblem and provides a conic feasible primal-dual initial point for the self-dual embedding model by solving two auxiliary linear optimization problems. Numerical results on test problems in the CBLIB library show on average around 61% reduction of the IPM iterations for a variety of MISOCO problems. 3 - The Tight-and-cheap Conic Relaxation for the AC Optimal Power Flow Problem Miguel F. Anjos, Professor, NSERC-Hydro-Quebec-Schneider Electric Industrial Research Chair, Inria International Chair, P.O. Box 6079, Station Centre-Ville, Montreal, QC, H3C 3A7, Canada, Christian Bingane, Sebastien Le Digabel The classical ACOPF problem is highly non-convex and generally hard to solve. Convex relaxations, in particular, semidefinite, second-order cone, and linear relaxations have recently attracted significant interest. The semidefinite relaxation is the strongest among them and is exact for many cases, but the computational efficiency for solving large-scale semidefinite optimization is limited. We propose a new conic relaxation which is derived by a combination of semidefinite optimization and the reformulation-linearization technique. The proposed relaxation is stronger than the second-order cone relaxation and nearly as tight as the semidefinite relaxation. 4 - Valid Conic Inequalities for Hyperboloids and Non-convex Quadratic Cones Julio C. Góez, Miguel F. Anjos We use the disjunctive conic cut (DCC) approach to show the existence of valid conic inequalities for hyperboloids and non-convex quadratic cones when the disjunction is defined by parallel hyperplanes. For some of the cases, we show that for each of the branches of those sets, which are convex, the intersections with the DCCs provides the convex hull of the intersection of the branches with a parallel linear disjunction. For other cases, we show that this tecnique provides a second order cone equivalent reformulation for some non convex sets.

32