Linear Programming

Computational aspects of simplex and MBU-simplex algorithms using different anti-cycling pivot rules

  • Nagy Adrienn
  • Tibor Illés
    • Categories Linear Programming, Optimization Software Benchmark Tags , , ,

    Several variations of index selection rules for simplex type algorithms for linear programming, like the Last-In-First-Out or the Most-Often-Selected-Variable are rules not only theoretically finite, but also provide significant flexibility in choosing a pivot element. Based on an implementation of the primal simplex and the monotonic build-up (MBU) simplex method, the practical benefit of the … Read more

    Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization

  • Nicolas Gillis
  • Robert Luce
    • Categories Data-Mining, Linear Programming Tags , , , , ,

    Nonnegative matrix factorization (NMF) has been shown recently to be tractable under the separability assumption, under which all the columns of the input data matrix belong to the convex cone generated by only a few of these columns. Bittorf, Recht, R\’e and Tropp (`Factoring nonnegative matrices with linear programs’, NIPS 2012) proposed a linear programming … Read more

    Novel update techniques for the revised simplex method

  • J. A. Julian Hall
  • Qi Huangfu
    • Categories Linear Programming

    This paper introduces three novel techniques for updating the invertible representation of the basis matrix when solving practical sparse linear programming (LP) problems using a high performance implementation of the dual revised simplex method, being of particular value when suboptimization is used. Two are variants of the product form update and the other permits multiple … Read more

    Calmness modulus of linear semi-infinite programs

  • M.J. Cánovas
  • Alexander Y. Kruger
  • Marco A. López
  • J. Parra
  • Michel Thera
    • Categories Linear Programming, Semi-infinite Programming Tags , , , ,

    Our main goal is to compute or estimate the calmness modulus of the argmin mapping of linear semi-infinite optimization problems under canonical perturbations, i.e., perturbations of the objective function together with continuous perturbations of the right-hand side of the constraint system (with respect to an index ranging in a compact Hausdorff space). Specifically, we provide … Read more

    Robustness Analysis of HottTopixx, a Linear Programming Model for Factoring Nonnegative Matrices

  • Nicolas Gillis
    • Categories Data-Mining, Linear Programming Tags , , , ,

    Although nonnegative matrix factorization (NMF) is NP-hard in general, it has been shown very recently that it is tractable under the assumption that the input nonnegative data matrix is separable (that is, there exists a cone spanned by a small subset of the columns containing all columns). Since then, several algorithms have been designed to … Read more

    Improving an interior-point approach for large block-angular problems by hybrid preconditioners

  • Silvana Bocanegra
  • Jordi Castro
  • Aurelio Ribeiro Leite Oliveira
    • Categories Linear Programming

    The computational time required by interior-point methods is often dominated by the solution of linear systems of equations. An efficient specialized interior-point algorithm for primal block-angular problems has been used to solve these systems by combining Cholesky factorizations for the block constraints and a conjugate gradient based on a power series preconditioner for the linking … Read more

    Solving Security Constrained Optimal Power Flow Problems by a Structure Exploiting Interior Point Method

  • Naiyuan Chiang
  • Andreas Grothey
    • Categories Applications - OR and Management Sciences, Linear Programming, Stochastic Programming Tags

    The aim of this paper is to demonstrate a new approach to solve the linearized (n-1) security constrained optimal power flow (SCOPF) problem by a structure exploiting interior point solver. Firstly, we present a reformulation of the linearized SCOPF model, in which most matrices that need to be factorized are constant. Hence, most factorizations and … Read more

    A new warmstarting strategy for the primal-dual column generation method

  • Jacek Gondzio
  • Pablo Gonzalez-Brevis
    • Categories Cutting Plane Approaches, Linear Programming Tags , , , ,

    This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after … Read more

    Factoring nonnegative matrices with linear programs

  • Victor Bittorf
  • Christopher Re
  • Benjamin Recht
  • Joel Tropp
    • Categories Data-Mining, Linear Programming Tags , , , , ,

    This paper describes a new approach for computing nonnegative matrix factorizations (NMFs) with linear programming. The key idea is a data-driven model for the factorization, in which the most salient features in the data are used to express the remaining features. More precisely, given a data matrix X, the algorithm identifies a matrix C that … Read more

    ON AN EFFICIENT IMPLEMENTATION OF THE FACE ALGORITHM FOR LINEAR PROGRAMMING

  • Zhang Lei-Hong
  • Weihong Yang
  • Lizhi Liao
    • Categories Linear Programming Tags , , ,

    In this paper, we consider the solution of the standard linear programming (LP). A remarkable result in LP claims that all optimal solutions form an optimal face of the underlying polyhedron. In practice, many real-world problems have infinitely many optimal solutions and pursuing the optimal face, not just an optimal vertex, is quite desirable. The … Read more