PCx - primal-dual interior-point code for linear programming

PCx probname[.mps]

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 [em] solution of a linear system with a large, sparse positive definite coefficient matrix [em] 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 [em] see mps(5). PCx does not solve integer linear programs.

PCx has no command-line options.

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

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.

[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.

/usr/share/doc/pcx/PCx-user.ps.gz, mps(5)

This manual page was written by James R. Van Zandt <jrv@debian.org>, for the Debian GNU/Linux system (but may be used by others).