ESTS1145 PCX.

PCX, Interior-Point Linear Programming Solver

NAME OR DESIGNATION OF PROGRAM, COMPUTER, DESCRIPTION OF PROGRAM OR FUNCTION, METHODS, RESTRICTIONS ON THE COMPLEXITY OF THE PROBLEM, TYPICAL RUNNING TIME, UNUSUAL FEATURES, RELATED OR AUXILIARY PROGRAMS, STATUS, REFERENCES, HARDWARE REQUIREMENTS, LANGUAGE, SOFTWARE REQUIREMENTS, OTHER PROGRAMMING OR OPERATING INFORMATION OR RESTRICTIONS, NAME AND ESTABLISHMENT OF AUTHORS, MATERIAL, CATEGORIES

[ top ]

1. NAME OR DESIGNATION OF PROGRAM: PCX.

[ top ]

2. COMPUTERS

To submit a request, click below on the link of the version you wish to order. Only liaison officers are authorised to submit online requests. Rules for requesters are available here.

Program name	Package id	Status	Status date
PCX	ESTS1145/02	Tested	19-FEB-2004

Machines used:

Package ID	Orig. computer	Test computer
ESTS1145/02	UNIX W.S.,PC Windows	PC Pentium III,Linux-based PC,DEC ALPHA W.S.

[ top ]

3. DESCRIPTION OF PROGRAM OR FUNCTION

PCX solves linear programming problems using the Mehrota predictor-corrector interior-point algorithm. PCX can be called as a subroutine or used in stand-alone mode, with data supplied from an MPS file. The software incorporates modules that can be used separately from the linear programming solver, including a presolve routine and data structure definitions.

[ top ]

4. METHODS

The Mehrota predictor-corrector method is a primal-dual interior-point method for linear programming. The starting point is determined from a modified least squares heuristic. Linear systems of equations are solved at each interior-point iteration via a sparse Cholesky algorithm native to the code. A presolver is incorporated in the code to eliminate inefficiencies in the user's formulation of the problem.

[ top ]

5. RESTRICTIONS ON THE COMPLEXITY OF THE PROBLEM

There are no size limitations built into the program. The size of problem solved is limited by RAM and swap space on the user's computer.

[ top ]

6. TYPICAL RUNNING TIME

Time required for execution depends on the size and properties of each individual problem. Test problems require as little as 0.2 seconds and as much as 12 hours on a SUN SPARCstation-5.

[ top ]

7. UNUSUAL FEATURES

PCX is freely available linear programming code with reusable code modules, and reusable data structure.

[ top ]

8. RELATED OR AUXILIARY PROGRAMS

Solvers that implement a similar algorithm are available commercially; examples include LOQO, OSL (from IBM), CPLEX barrier (from CPLEX, INC.). PCX uses a freely available Fortran code for direct sparse Cholesky factorization written by Esmond Ng and Barry Peyton at Oak Ridge National Laboratory, incorporating a multiple-minimum-degree ordering code written by Joseph Liu and the University of Waterloo, Waterloo, Ontario, Canada.

[ top ]

9. STATUS

Package ID	Status date	Status
ESTS1145/02	19-FEB-2004	Tested at NEADB

[ top ]

10. REFERENCES

ESTS1145/02, included references:

- Joseph Czyzyk, Sanjay Mehrotra, Michael Wagner, and Stephen J. Wright
PCx User Guide (version 1.1)
Technical Report OTC 96/01 (November 3, 1997)

[ top ]

11. HARDWARE REQUIREMENTS: At least 8 Mbytes of RAM is recommended.

[ top ]

12. PROGRAMMING LANGUAGE(S) USED

Package ID	Computer language
ESTS1145/02	C-LANGUAGE, FORTRAN

[ top ]

13. SOFTWARE REQUIREMENTS

JAVA runtime environment in order to use the graphical user interface.

[ top ]

14. OTHER PROGRAMMING OR OPERATING INFORMATION OR RESTRICTIONS

The READMPS file contains instructions for installing the program and MAKEFILE the instructions for using the make program to compile the software. Both are included in the software package as distributed.

[ top ]

15. NAME AND ESTABLISHMENT OF AUTHORS: J. Czyzyk
Argonne National Lab., IL
U.S.A.

[ top ]

16. MATERIAL AVAILABLE

ESTS1145/02

File name	File description	Records
build	build script
PCx-user.ps	user's guide
MAKEARCH	architecture specific make files
DEC	DEC ALPHA Output files
LINUX	LINUX Output files
WINDOWS2K	Windows 2000 Output files
WINDOWSXP	Windows XP Output files
Ng-Peyton	Ng-Peyton solver source code and Makefile
PCx.dsp	Microsoft Visual Studio Project file
PCx.dsw	Microsoft Visual Studio Workspace file
pcxarch	Script to examine the architecture
PCxGUI.tar.gz	Java GUI
PCx.exe	DOS/Windows executable
SampleProblems	Sample problem input files
solveall	script to solve all sample problem
solveall.bat	script to solve all sample problem
SRC	c-source files of PCx

[ top ]

17. CATEGORIES

P. General Mathematical and Computing System Routines

Keywords: algorithms, iterative methods, linear programming, optimization.