Informs Annual Meeting 2017

TD76

INFORMS Houston – 2017

TD74

2 - Large Gaps Between Cyclic Coordinate Descent and Randomized Versions Ruoyu Sun, UIUC, 104 S Mathew Ave, Urbana, IL, 61801, United States, ruoyus@illinois.edu A simple idea for solving large-scale computational problems is to iteratively solve smaller subproblems, which appeared in, e.g., Gauss-Seidel (G-S), Kaczmarz, coordinate descent (CD). We prove that for all these methods, there are large gaps between the deterministic cyclic versions and the randomized versions. In fact, we show an (up to) O(n^2) gap in the convergence rate for CD/G-S/Kaczmarz methods. There are examples showing cyclic CD (C-CD) can be much slower than randomized coordinate descent (R-CD), but there also exist practical examples where C-CD is faster. We show that C-CD indeed can be O(n^2) slower than R- CD in the worst case, by establishing a lower bound that matches the upper bound. 3 - Surpassing Gradient Descent Provably: A Cyclic Incremental Method with Linear Convergence Rate Aryan Mokthari, University of Pennsylvania, 220 South 33rd Street, 107 Towne Building, Philadelphia, PA, 19104, United States, aryanm@seas.upenn.edu The coordinate descent (CD) methods have seen a resurgence of recent interest because of their applicability in machine learning as well as large scale data analysis and superior empirical performance. CD methods have two variants, cyclic coordinate descent (CCD) and randomized coordinate descent (RCD) which are deterministic and randomized versions of the CD methods. In light of the recent results in the literature, there is the common perception that RCD always dominates CCD in terms of performance. In this paper, we provide problem classes for which CCD (or CD with any deterministic order) is provably faster than RCD in terms of asymptotic worst-case convergence. 4 - When Cyclic Coordinate Descent Beats Randomized Coordinate Descent The coordinate descent (CD) methods have seen a resurgence of recent interest because of their applicability in machine learning as well as large scale data analysis and superior empirical performance. CD methods have two variants, cyclic coordinate descent (CCD) and randomized coordinate descent (RCD) which are deterministic and randomized versions of the CD methods. In light of the recent results in the literature, there is the common perception that RCD always dominates CCD in terms of performance. In this paper, we provide problem classes for which CCD (or CD with any deterministic order) is provably faster than RCD in terms of asymptotic worst-case convergence. 372E Mixed Integer Programming with Applications Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Haochen Luo, Texas A&M University, College Station, TX, 77840, United States, hcluo@tamu.edu 1 - Chance Constrained Combinatorial Optimization with a Probability Oracle A chance-constrained combinatorial optimization problem (CCOP) aims to find a minimum cost selection of binary decisions, which satisfies a constraint with high probability. Suppose that we have an oracle that can compute the probability of satisfying the constraint exactly. Using this oracle, we propose a general method for solving CCOP exactly. In addition, if CCOP is solved by a sampling-based approach, the oracle can be used as a tool for checking and fixing the feasibility of the resulting solution. To demonstrate the effectiveness of the proposed methods, we apply them to an NP-hard probabilistic set covering problem, which admits a polynomial-time exact probability oracle. 2 - Preventive Maintenance Scheduling with Shared Set-ups Eric C. Blair, University of Florida, 25 SW 5th Terrace, Apt. 4506, Gainesville, FL, 32601, United States, ecblair@ufl.edu, Yongpei Guan We present a formulation of a preventive maintenance scheduling problem with shared set-ups. Maintenance jobs have a time-variant interval which they must be performed within, and some jobs share set-ups, so scheduling these jobs together can reduce set-up costs. The problem is modeled as an integer program, and can be relaxed to a linear program without sacrificing integrality when excluding complicating capacity constraints. We explore and discuss approaches that can be used to generate solutions for large-scale instances of the problem with all constraints included. Mert Gurbuzbalaban, Researcher/Postdoctoral Associate, Rutgers University, Cambridge, MA, 02139, United States, mg1366@business.rutgers.edu TD76 Hao-Hsiang Wu, University of Washington, Seattle, WA, United States, hhwu2@uw.edu, Simge Kucukyavuz

372C OR and Computational Biology Sponsored: Computing Sponsored Session

Chair: Allen Holder, Rose-Hulman Institute of Technology, Terre Haute, IN, 47803, United States, holder@rose-hulman.edu 1 - Modeling Cellular Metabolism as a Hypergraph Flow Paul Brooks, Virginia Commonwealth Univ., Dept of Stat. Sci. and OR, P.O. Box 843083, Richmond, VA, 23284, United States, jpbrooks@vcu.edu Optimization-based models of metabolism are a widely used tool in systems biology for generating predictions in medical and engineering applications. We explain how this modeling paradigm is essentially a study of flows in hypergraphs. We then demonstrate how optimal flux distributions can be decomposed into flows along pathways in a manner that enhances model interpretation. The method is applied to study the virulence of an infection- causing strain of Salmonella. 2 - Mixed-Integer Program and Heuristics for Monogamous Relationship Inference In this study, we infer the relationships of parents and offspring in monogamous mating process. The inference of monogamous relationships is a NP-Hard combinatorial problem with the objective to minimize the number of parents, subject to the biological constraints (i.e., Mendelian laws). A heuristic approach is proposed to find the best monogamous parent information. 3 - Inferring New Protein Function with DEA Allen Holder, Rose-Hulman Institute of Technology, Department of Mathematics, Terre Haute, IN, 47803, United States, holder@rose-hulman.edu Proteins are classified into functionally similar classes called families. However, proteins probably don’t have unique functionality, and hence, they likely share membership with families other than their original classification. We use a robust, inverse DEA model to help infer new functional relationships. 4 - New Density-based Optimization Formulations and Algorithms to Identify Fixations in Gaze Data Wen Liu, Doctoral Student, Worcester Polytechnic Institute, 100 Institute Rd., Worcester, MA, 01609, United States, wliu3@wpi.edu, Andrew C.Trapp, Soussan Djamasbi Eye tracking is an increasingly common technology with a variety of practical uses. Gaze data can be categorized into two main events: fixations, which represent attention, and saccades, which occur between fixations. We develop new optimization formulations to recover densest fixations, extending earlier work that identifies fixations using a novel density metric. We discuss related complexity results and demonstrate a polynomial-time algorithm exists if the number of fixations is apriori fixed, and very small. We conclude with encouraging computational results and insights on real data sets. 372D Optimization for large-scale data analysis Sponsored: Optimization, Nonlinear Programming Sponsored Session Chair: Mert Gurbuzbalaban, Rutgers University, 77 Massachusetts Avenue, Building 32, Room D632, Cambridge, MA, 02139, United States, mg1366@business.rutgers.edu 1 - Optimal Design of Efficient Rooftop Photovoltaic Arrays Madeleine Udell, Cornell University, 207 Hoy Road, Ithaca, NY, 14850, United States, udell@cornell.edu, Alp Yurtsever, Joel Tropp, Volkan Cevher In this talk, we consider a fundamental class of convex matrix optimization problems with low-rank solutions. We show it is possible to solve these problem using far less memory than the natural size of the decision variable when the problem data has a concise representation. Our proposed method, SketchyCGM, is the first algorithm to offer provable convergence to an optimal point with an optimal memory footprint. Chun-An Chou, Northeastern University, Boston, MA, United States, ch.chou@northeastern.edu, Daehan Won, Tanja Berger-Wolf, W. Art Chaovalitwongse TD75

403