linear programming

A New and Efficient Large-Update Interior-Point Method for Linear Optimization

  • Jiming Peng
  • Cornelis Roos
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    Recently, the authors presented a new large-update primal-dual method for Linear Optimization, whose $O(n^\frac23\,\log\frac{n}{\e})$ iteration bound substantially improved the classical bound for such methods, which is $O\br{n\log\frac{n}{\e}}$. In this paper we present an improved analysis of the new method. The analysis uses some new mathematical tools developed before when we considered a whole family of … Read more

    An Interior-Point Approach to Sensitivity Analysis in Degenerate Linear Programs

  • Michael J. Todd
  • E. Alper Yildirim
    • Categories Linear Programming Tags , ,

    We consider the interior-point approach to sensitivity analysis in linear programming (LP) developed by the authors. We investigate the quality of the interior-point bounds under degeneracy. In the case of a special degeneracy, we show that these bounds have the same nice relationship with the optimal partition bounds as in the nondegenerate case. We prove … Read more

    Hyper-sparsity in the revised simplex method and how to exploit it

  • J. A. Julian Hall
  • Kenneth McKinnon
    • Categories Linear Programming Tags , ,

    The revised simplex method is often the method of choice when solving large scale sparse linear programming problems, particularly when a family of closely-related problems is to be solved. Each iteration of the revised simplex method requires the solution of two linear systems and a matrix vector product. For a significant number of practical problems … Read more

    Warm start strategies in interior-point methods for linear programming

  • Stephen Wright
  • E. Alper Yildirim
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We study the situation in which, having solved a linear program with an interior-point method, we are presented with a new problem instance whose data is slightly perturbed from the original. We describe strategies for recovering a “warm-start” point for the perturbed problem instance from the iterates of the original problem instance. We obtain worst-case … Read more

    A New Class of Polynomial Primal-Dual Methods for Linear and Semidefinite Optimization

  • Cornelis Roos
  • J Peng
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    We propose a new class of primal-dual methods for linear optimization (LO). By using some new analysis tools, we prove that the large update method for LO based on the new search direction has a polynomial complexity $O\br{n^{\frac{4}{4+\rho}}\log\frac{n}{\e}}$ iterations where $\rho\in [0,2]$ is a parameter used in the system defining the search direction. If $\rho=0$, … Read more