2016 INFORMS Annual Meeting Program

WD14

INFORMS Nashville – 2016

WD13 104C-MCC Computational Optimization and Software Sponsored: Optimization, Computational Optimization and Software Sponsored Session Chair: Robert J Vanderbei, Princeton University, Princeton, NJ, 08544, United States, rvdb@princeton.edu Co-Chair: Hande Benson, Drexel University, LeBow College of Business, Philadelphia, PA, 19104, United States, benson@drexel.edu 1 - Cubic Regularization For Conjugate Gradient Minimization And Symmetric Rank-one Methods Hande Benson, Drexel University, benson@drexel.edu Regularization techniques have been used to help existing algorithms solve “difficult” nonlinear optimization problems. Over the last decade, regularization has been proposed to remedy issues with equality constraints and equilibrium constraints, bound Lagrange multipliers, and identify infeasible problems. In this talk, we will focus on the application of cubic regularization in the context of the symmetric rank-one and conjugate gradient methods for nonlinear programming. 2 - Two New Efficient Algorithms For Compressed Sensing Robert J Vanderbei, Princeton University, rvdb@princeton.edu We present two new approaches for solving large-scale compressed sensing problems. The first approach uses the parametric simplex method to recover very sparse signals by taking a small number of simplex pivots while the second approach reformulates the problem using Kronecker products to achieve faster computation via a sparser problem formulation. Numerical studies show that each of these two algorithms are about 10 times faster than current state-of-the-art methods. 3 - Using A Fast Projected Gradient Method To Solve Large Scale Nonlinear Optimization Problems. Igor Griva, George Mason University, igriva@gmu.edu Some modern nonlinear optimization problems have a large number of variables and dense Hessians that makes challenging or impossible using second order methods. We discuss how the fast projected gradient method can be used for addressing optimization problems in machine learning, nonnegative least squares and positive emission tomography reconstruction. Facility Location I Contributed Session Chair: David Mendez, Graduate Student, University of Tennessee, 2621 Morgan Circle, Knoxville, TN, 37996, United States, dmendez@vols.utk.edu 1 - The Price Of Deception In Social Choice James Patrick Bailey, Georgia Institute of Technology, 755 Ferst Drive, NW, Unit 2401, Atlanta, GA, 30332, United States, james.bailey@gatech.edu, Craig Aaron Tovey Classic impossibility theorems rule out strategy-proofness for all popular voting rules, but is it wise to always settle for nothing with respect to manipulation? We introduce a measure, the price of deception, of how much strategic voting could alter an election outcome with respect to the winning criterion. We analyze this measure for several standard voting rules and find significant differences among them. We also analyze several standard cost functions for facility location, and again find large differences. These results give good evidence that the price of deception, like computational complexity, does offer finer distinctions of manipulability than between ”yes” or ”no”. 2 - A Comprehensive Model For Location/allocation Of Maritime Search And Rescue Vessels Amin Akbari, PhD Candidate, Dalhousie University, 1104-1094 The general methodology utilized in this study is building a mathematical model to optimize the Location/Allocation of Maritime Search and Rescue Resources with regard to several criteria such as primary and backup coverage, mean access time and service equality. A multi-objective model is built to optimize the location and response allocation of SAR resources with simultaneously taking several objectives into account in order to achieve greater responsiveness and resource utilization. Atlantic Canada serves as the area of the study. Sensitivity analyses are performed on variable objective weights and other parameters to examine their impact on the optimal solution. Wellington Street, Halifax, NS, B3H 2Z9, Canada, amin.akbari@dal.ca, Ronald P Pelot, H A Eiselt WD14 104D-MCC

2 - Effects Of Disjunctive Conic Cuts Within A Branch And Conic Cut Algorithm Sertalp Bilal Cay, Lehigh University, sertalpbilal@gmail.com Recently, Mixed Integer Second Order Cone Optimization (MISOCO) has gained attention. This interest has been driven by the availability of efficient methods to solve second order cone optimization (SOCO) problems and the wide range of applications of MISOCO. In this work, we experiment with the recently developed methodology of Disjunctive Conic Cuts (DCC). In particular, we test it on variations of portfolio optimization problems within a Branch and Conic Cut (BCC) framework. Our experiments show that our proposed methodology using DCCs is effective in practical settings. 3 - A Rounding Procedure For A Maximally Complementary Solution Of Second Order Conic Optimization Ali Mohammad Nezhad, Lehigh, alm413@lehigh.edu The concept of optimal partition was originally introduced for linear optimization, and later the concept was extended to second-order conic optimization. In this paper, we present a rounding procedure, which uses optimal partition information to generate a pair of maximally complementary optimal solutions. The rounding procedure starts from a strictly interior solution, close to the optimal set. It either gives an exact maximally complementary optimal solution in strongly polynomial time, or provides a fast iterative procedure to approximate a maximally complementary optimal solution. WD12 104B-MCC Recent Advances in Discrete Optimization Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Andres Gomez Escobar, University of California, Berkeley, CA, United States, a.gomez@berkeley.edu 1 - Final Point Generalized Intersection Cuts Aleksandr Mark Kazachkov, Carnegie Mellon University, akazachk@cmu.edu We introduce a new class of cuts for mixed-integer programming called final point cuts. Generated from arbitrary valid disjunctions, this class is an extension of the generalized intersection cut paradigm. We present theoretical and computational results demonstrating the strength of these cuts as compared to both standard intersection cuts and previous types of generalized intersection cuts. 2 - Generating Cuts From The Ramping Polytope For The Unit Commitment Problem Jim Ostrowski, University of Tennessee, jostrows@utk.edu We present a perfect formulation for a single generator in the unit commitment (UC) problem. This generator can have characteristics such as ramping constraints, time-dependent start-up costs, and start-up/shut-down ramping. The perfect formulation is polynomially large, so we use it to create a cut-generating linear program for a single generator. We test the computational efficacy of these cuts in a utility-scale UC MIP model, based on the FERC generator set and 2015 hourly data from PJM. These cuts may also beneficial for the more complex UC models used by ISOs today because they reduce the enumeration needed to enforce a generator’s technical constraints. 3 - Conic Quadratic Program With Indicator Variables We investigate a conic quadratic mixed 0-1 programming problem with on-off constraints that arises from mean risk optimization. Analysis is conducted on the properties of the optimal solutions of the problem and its relaxation. A class of linear valid inequalities is derived by lifting the extended polymatroid inequalities that are known to be highly effective for the pure 0-1 case. We report the result of computational experiments to demonstrate the impact of the inequalities on strengthening the continuous relaxation. 4 - Polymatroid Inequalities For Mixed-integer Second Order Cone Programming Andres Gomez, University of California Berkeley, a.gomez@berkeley.edu, Alper Atamturk We propose valid inequalities for mixed-integer second order cones programs. We show that the proposed inequalities completely describe the convex hull of a single second order cone constraint. Moreover we show how to strengthen the inequalities using other constraints of the optimization problem. We report computational experiments on mixed-integer second-order cone programs, using the proposed valid inequalities as cutting planes. Hyemin Jeon, University of California Berkeley, hyemin.jeon@berkeley.edu, Alper Atamturk

459