man PCx (1): primal-dual interior-point code for linear programming

SYNOPSIS

PCx probname[.mps]

DESCRIPTION

This manual page documents briefly the PCx command. PCx has more detailed documentation in PostScript format; see [1].

PCx is a freely available primal-dual interior-point code for linear programming. It implements Mehrotra's predictor-corrector algorithm, the algorithm that forms the basis of most existing interior-point codes for general linear programming. The major computational operation --- solution of a linear system with a large, sparse positive definite coefficient matrix --- is performed with the sparse Cholesky package of Ng and Peyton (Oak Ridge National Laboratory), with minor modifications to handle small pivot elements.

PCx accepts any valid linear program that can be specified in the MPS format --- see mps(5). PCx does not solve integer linear programs.

OPTIONS

PCx has no command-line options.

PARAMETERS

PCx allows many parameters and options to be set by the user. These quantities are read from a specifications file. If the name of the MPS input file is probname.mps, PCx looks for the following files, in order:

        probname.spc
        probname.specs
        spc
        specs
        PCx.specs

If more than one of these files exist, PCx uses the first file in the list and ignores the others.

The following keywords can be used in the specifications file, together with their default settings. The file should contain one such keyword per line, together with its corresponding numerical value or option, if appropriate. The file is processed sequentially from beginning to end, so the effect of any line can be undone by a later line. For keywords with a yes/no argument, omission of the argument will be taken to mean yes. Note that the default setting is not necessarily yes. Case is not significant in keywords.

min [ yes | no ]: Minimize the objective (default).
max [ yes | no ]: Maximize the objective.
inputdirectory: If PCx is to search for the MPS input files in another directory, in addition to the current working directory, name this other directory here. Include a trailing "/". PCx always looks first in the current working directory. The output and history files are always written to the working directory.
solution [ yes | no ]: Specify whether to write a solution file probname.out in the current working directory. Default: yes.
history [ yes | no ]: Specify whether to write a history file probname.log in the working directory. Default: yes.
objectivename name: Request the objective cost vector to be the specific row name in probname.mps. Default: the first row of type "N" in probname.mps is taken to be the objective.
rhsname name: Request the right-hand side to be the specific column name in probname.mps. Default: the first RHS encountered in the MPS file.
rangename name: Request the range to be the specific column name in probname.mps. Default: the first RANGE encountered in the MPS file.
boundname name: Request the bound to be the specific column name in probname.mps. Default: the first BOUND in the MPS file.
presolve [ yes | no ]: Specify whether or not to perform presolving. The purpose of presolving is to detect and handle redundant information, producing a smaller problem to be solved by the actual linear programming algorithm [2]. Default: yes.
preprocess [ yes | no ]: Same as presolve.
cachesize value: Specify the size of the cache on the machine, in kilobytes. Any value in the range 0-2048 is acceptable. Specify 0 for Cray machines. This parameter is used by the Ng-Peyton sparse Cholesky code. Default: 16.
centerexp value: Specify the exponent to be used for calculation of the centering parameter sigma. Any real value in the range 1.0-4.0 is allowable. Default: 3.0.
opttol value: Specify an optimality tolerance. Default: 1.e-8.
prifeastol value: Specify a primal feasibility tolerance. Default: 1.e-8.
dualfeastol value: Specify a dual feasibility tolerance. Default: 1.e-8.
unrollinglevel num: Specify the level of loop unrolling. Allowable values are 1, 2, 4, and 8. This parameter is used only in the Ng-Peyton Cholesky code. Default: 4.
iterationlimit num: Specify an upper limit on the number of iterations. The algorithm terminates in suboptimal status if it exceeds this many iterations without satisfying any of the termination conditions. Any positive integer is allowable. Default: 100.
refinement [ yes | no ]: Specify whether to perform preconditioned conjugate gradient refinement of the computed solution to the linear system if it has a relative residual larger than the parameter prifeastol. Default: no.
stepfactor value: Specify a value in the range (0, 1) that is used in Mehrotra's adaptive steplength heuristic from [3]. Default: 0.9.
scaling [ yes | no ]: Specify whether or not row and column scaling [4] is performed on the constraint matrix. Default: yes.
HOCorrections [ yes | no ]: Specify whether Gondzio's higher-order corrections [5] are used to enhance the search direction. Default: yes.
MaxCorrections value: If HOCorrections=yes, this parameter is an upper limit on the number of Gondzio's higher-order corrections allowed at each iteration. If value=0, the maximum is determined automatically by PCx according to the relative cost of factorization and solve operations. if HOCorrections=no, this parameter is ignored. Default: 0.

REFERENCES

[1] J. Czyzyk et al., "PCx User Guide (Version 1.1)", Optimization Technology Center, Technical Report OTC 96/01, November 3, 1997.
[2] E. D. Andersen and K. D. Andersen, "Presolving in linear programming", Mathematical Programming, 71 (1995), pp. 221-245.
[3] S. Mehrotra, "On the implementation of a primal-dual interior point method", SIAM Journal on Optimization, 2 (1992), pp 575-601.
[4] A. R. Curtis and J. K. Reid, "On the automatic scaling of matrices for Gaussian elimination", J. Inst. Maths Applics, 10 (1972), pp. 118-124.
[5] J. Gondzio, "Multiple centrality corrections in a primal-dual method for linear programming", Computational Optimization and Applications, 6 (1996), pp. 137-156.

AUTHOR

This manual page was written by James R. Van Zandt <[email protected]>, for the Debian GNU/Linux system (but may be used by others).