PCx user guide

Joseph Czyzyk, Sanjay Mehrotra, Stephen J. Wright1997 · DOI

TL;DR

This paper introduces PCx, a primal-dual interior-point solver for linear programming problems. It details the algorithm's formulation, implementation, and usage, demonstrating its efficiency on standard test problems and highlighting its modular design for extensibility.

What Problem Does This Paper Address?

Linear programming (LP) is a fundamental optimization technique used across many scientific and engineering disciplines. Solving large-scale LP problems efficiently is crucial. Interior-point methods have emerged as a powerful class of algorithms for LP, offering competitive performance compared to traditional simplex methods. This paper addresses the need for a robust, efficient, and user-friendly interior-point solver by presenting PCx, a primal-dual interior-point code. The authors aim to provide a comprehensive guide to its formulation, algorithmic underpinnings, and practical application, including installation and usage instructions, and to report on its performance.

Methods

PCx implements a variant of Mehrotra's predictor-corrector algorithm, enhanced with Gondzio's higher-order correction strategy. This primal-dual approach is known for its efficiency in solving general linear programs. The core of the computational engine relies on a sparse Cholesky factorization code developed by Ng and Peyton, which has been modified to handle small pivot elements that can arise in interior-point methods.

Key methodological aspects include:

  • Problem Formulation: PCx accepts problems in the standard MPS format and converts them internally to a simplified LPtype formulation. It also handles transformations to a normal equations form for algorithmic purposes.
  • Algorithm: The algorithm iteratively refines a primal-dual solution by solving systems of linear equations derived from Newton's method applied to the Karush-Kuhn-Tucker (KKT) conditions. It incorporates a "centering" component and higher-order corrections to improve accuracy and convergence.
  • Linear Algebra: A significant focus is placed on efficient sparse matrix factorization. The Ng-Peyton Cholesky code is used, with modifications for numerical stability. Techniques like block elimination and Sherman-Morrison-Woodbury updates are employed to handle dense columns. Preconditioned conjugate gradient (PCG) is used for refinement when necessary.
  • Presolver: PCx includes a presolver that detects and handles redundant information in the LP model (e.g., infeasibility, empty rows/columns, duplicate rows/columns, fixed variables, singleton rows/columns, forced rows) to reduce problem size and complexity before the main algorithm is applied.
  • Specifications File: Users can control algorithmic parameters and options through a specifications file, allowing customization of tolerances, iteration limits, and other settings.

Datasets

The paper evaluates PCx on the standard NETLIB test set, which comprises a collection of feasible and infeasible linear programming problems. Additionally, it includes results for NEMS problems, which are derived from models used by the U.S. Department of Energy for electricity capacity planning, petroleum marketing, and coal marketing.

Key Insights and Ideas

  • Primal-Dual Interior-Point Methods are Highly Effective: The paper reinforces the notion that primal-dual interior-point methods, particularly with predictor-corrector steps and higher-order corrections, are very efficient for a broad range of LP problems.
  • Robustness through Presolving and Numerical Stability: The inclusion of a sophisticated presolver significantly enhances efficiency by reducing problem size. Modifications to the sparse Cholesky factorization to handle small pivots are crucial for numerical stability in interior-point methods.
  • Modular Design for Extensibility: The code's modular structure is highlighted as a key feature, encouraging users to experiment with variants of the algorithm and contributing to its ongoing development.
  • Importance of Efficient Linear Algebra: The performance of PCx is heavily dependent on the efficiency of its sparse linear algebra routines, particularly the Cholesky factorization. The paper details optimizations and modifications made to achieve this.

Key Results

PCx version 1.0 was executed on various Unix environments and tested on the NETLIB and NEMS problem sets.

  • Feasible Problems (Table 1): PCx correctly identified most feasible problems as optimal. In a few cases, it terminated with an "unknown" status, but the returned points were close to optimality. No feasible problems were incorrectly flagged as infeasible.
  • Infeasible Problems (Table 2): PCx correctly identified infeasibility for most problems. In some cases, infeasibility was detected by the presolver, avoiding the need to call the interior-point solver. A few problems terminated with "unknown" status.
  • NEMS Problems (Table 3): PCx solved these problems efficiently.
  • Performance: The paper reports computational results in terms of problem dimensions (before and after presolving), measures of infeasibility and complementarity, primal objective values, number of iterations, and CPU time. The results generally show good performance, with CPU times being competitive. The impact of higher-order corrections was noted as not always dramatic, partly due to the efficiency of the factorization routine relative to the solution routine.

Limitations and Future Work

  • Work in Progress: The authors explicitly state that PCx should be viewed as a work in progress.
  • Future Features: Potential future additions include finite termination/basis recovery and alternative linear algebra solvers or formulations of the step equations.
  • User Involvement: The authors encourage others to become involved in the development and extension of PCx.
  • Scaling Impact: While scaling generally improves efficiency, it can occasionally lead to poorer performance, and the option to disable it is provided.
  • Termination Status: While generally accurate, there are instances where PCx terminates with an "unknown" status, indicating areas for potential improvement in convergence detection or robustness.

Summary updated

Abstract

We describe the code PCx, a primal-dual interior-point code for linear programming. Information is given about problem formulation and the underlying algorithm, along with instructions for installing, invoking, and using the code. Computational results on standard test problems are tabulated. The current version number is 1.0.
BibTeX
@misc{czyzyk1997pcx,
  author = {Joseph Czyzyk and Sanjay Mehrotra and Stephen J. Wright},
  title = {{PCx user guide}},
  year = {1997},
  doi = {10.2172/475586},
}

Loading related content...

Figure