Crash option, Crash tolerance
|
Crash option
|
i |
Default = 0 |
|
Crash tolerance |
r |
Default = 0.1 |
Except on restarts, a CRASH
procedure is used to select an initial basis from certain rows and columns
of the constraint matrix (A - I). The Crash
option i determines which rows and columns
of A are eligible initially, and how many times CRASH
is called. Columns of -I are used to pad the basis where
necessary.
|
i |
Meaning |
|
0 |
The initial basis contains only slack variables: B= I.
|
|
1 |
CRASH is called once,
looking for a triangular basis in all rows and columns of the matrix A. |
|
2 |
CRASH is called twice (if
there are nonlinear constraints). The first call looks for a triangular
basis in linear rows, and the iteration proceeds with simplex iterations
until the linear constraints are satisfied. The Jacobian is then
evaluated for the first major iteration and CRASH is
called again to find a triangular basis in the nonlinear rows (retaining
the current basis for linear rows). |
|
3 |
CRASH is called up to three
times (if there are nonlinear constraints). The first two calls
treat linear equalities and linear inequalities
separately. As before, the last call treats nonlinear rows before
the first major iteration. |
If i
1, certain
slacks on inequality rows are selected for the basis first. (If
i 2, numerical values are used to exclude slacks
that are close to a bound.) CRASH then makes
several passes through the columns of A, searching for a basis
matrix that is essentially triangular. A column is assigned to "pivot''
on a particular row if the column contains a suitably large element in
a row that has not yet been assigned. (The pivot elements ultimately
form the diagonals of the triangular basis.) For remaining unassigned
rows, slack variables are inserted to complete the basis.
The Crash tolerance r allows
the starting procedure CRASH to ignore certain "small''
nonzeros in each column of A . If amax is the largest element in column j,
other nonzeros aij in the
column are ignored if |aij| 
amax x r.
(To be meaningful, r should be in the range 0 r < 1.)
When r > 0.0, the basis
obtained by CRASH may not be strictly triangular,
but it is likely to be nonsingular and almost triangular. The intention
is to obtain a starting basis containing more columns of A and
fewer (arbitrary) slacks. A feasible solution may be reached sooner
on some problems.
For example, suppose the first m columns
of A are the matrix shown under LU factor tolerance
; i.e., a tridiagonal matrix with entries -1, 4, -1. To help CRASH
choose all m columns for the initial
basis, we would specify Crash tolerance r for
some value of r > 1/4.