Computational experience with a primal-dual interior point method for linear programming (Q808184)

From MaRDI portal
Revision as of 01:17, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
Computational experience with a primal-dual interior point method for linear programming
scientific article

    Statements

    Computational experience with a primal-dual interior point method for linear programming (English)
    0 references
    0 references
    0 references
    0 references
    1991
    0 references
    This important paper describes the heuristics and implementation details used in the code OB1, which implements a primal-dual interior point algorithm for linear programming. The algorithm is motivated in terms of the logarithmic barrier function, and the strategy for choosing the initial point and the heuristic for decreasing the barrier parameter are described. The authors discuss the main computational engine of the code, namely, the preconditioned conjugate gradient algorithm for solving the sparse linear system of equations that arises at each iteration. The preconditioner is of the incomplete Cholesky type, but special care is needed in handling columns of the constraint matrix which destroy the sparsity of the coefficient matrix. Computational comparisons with the MINOS simplex code are given for problems in the expanded netlib test set.
    0 references
    computational experience
    0 references
    implementation
    0 references
    code OB1
    0 references
    primal-dual interior point algorithm
    0 references
    linear programming
    0 references
    logarithmic barrier function
    0 references
    preconditioned conjugate gradient algorithm
    0 references
    preconditioner
    0 references
    incomplete Cholesky type
    0 references
    MINOS simplex code
    0 references

    Identifiers