J. A. Julian Hall

A quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems

  • I. L. Galabova
  • J. A. Julian Hall
    • Categories Linear Programming

    This paper provides the first meaningful documentation and analysis of an established technique which aims to obtain an approximate solution to linear programming problems prior to applying the primal simplex method. The underlying algorithm is a penalty method with naive approximate minimization in each iteration. During initial iterations an approach similar to augmented Lagrangian is … Read more

    Parallelizing the dual revised simplex method

  • J. A. Julian Hall
  • Q. Huangfu
    • Categories Linear Programming, Parallel Algorithms

    This paper introduces the design and implementation of two parallel dual simplex solvers for general large scale sparse linear programming problems. One approach, called PAMI, extends a relatively unknown pivoting strategy called suboptimization and exploits parallelism across multiple iterations. The other, called SIP, exploits purely single iteration parallelism by overlapping computational components when possible. Computational … 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

    Parallel distributed-memory simplex for large-scale stochastic LP problems

  • Mihai Anitescu
  • J. A. Julian Hall
  • Miles Lubin
  • Cosmin G. Petra
    • Categories Linear Programming, Parallel Algorithms, Stochastic Programming Tags , , ,

    We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal … Read more

    Towards a practical parallelisation of the simplex method

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

    The simplex method is frequently the most efficient method of solving linear programming (LP) problems. This paper reviews previous attempts to parallelise the simplex method in relation to efficient serial simplex techniques and the nature of practical LP problems. For the major challenge of solving general large sparse LP problems, there has been no parallelisation … 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