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 —
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.
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
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.
[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 <
[email protected]>, for
the Debian GNU/Linux system (but may be used by others).