PCx - primal-dual interior-point code for linear programming
SYNOPSIS
PCxprobname[.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.
objectivenamename
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.
rhsnamename
Request the right-hand side to be the specific column name in
probname.mps. Default: the first RHS encountered in the MPS file.
rangenamename
Request the range to be the specific column name in
probname.mps. Default: the first RANGE encountered in the MPS file.
boundnamename
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.
cachesizevalue
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.
centerexpvalue
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.
opttolvalue
Specify an optimality tolerance. Default: 1.e-8.
prifeastolvalue
Specify a primal feasibility tolerance. Default: 1.e-8.
dualfeastolvalue
Specify a dual feasibility tolerance. Default: 1.e-8.
unrollinglevelnum
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.
iterationlimitnum
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.
stepfactorvalue
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.
MaxCorrectionsvalue
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.