Page 132 -

titre (titer) The reacting strength of a stand- In this case, the residual is r = Ax − b, and the
ard solution, usually expressed as the weight test has the form:
3
(mass) of the substance equivalent to 1 cm of
the solution. r ≤ t + t b ,
a
r
where is some norm.
token See term.
topological invariant A quantity enjoyed
tolerance approach An approach to sen- by a topological space which is invariant with
sitivity analysis in linear programming that respect to homeomorphisms.
expresses the common range that parameters can
occupy while preserving the character of the topological motif A subnetwork of the bio-
solution. In particular, suppose B is an optimal chemical network invariant under topological
basis and rim data changes by (Db, Dc). The transformation.
tolerance for this is the maximum value of t for Comment: See also biochemical, chemical,
which B remains optimal as long as |Db |≤ t dynamical, functional, kinetic, mechanistic,
i
for all i and |Dc |≤ t for all j. The tolerance for phylogenetic, regulatory, and thermodynamic
j
the basis, B, can be computed by simple linear motives.
algebra, using tableau information.
topological sort This sorts the nodes in a
network such that each arc, say kth, hasTail(k) <
tolerances Small positive values to control
Head(k) in the renumbered node indexes. This
elements of a computer implementation of an
arises in a variety of combinatorial optimization
algorithm. When determining whether a value,
problems, such as those with precedence con-
v, is nonnegative, the actual test is v> −t, where
straints. If the nodes cannot be topologically
t is an absolute tolerance. When comparing two
sorted, the network does not represent a partially
values to determine if u ≥ v, the actual test is
ordered set. This means, for example, there is
an inconsistency in the constraints, such as jobs
u − v ≤ t + t |v|, that cannot be sequenced to satisfy the asserted
r
a
precedence relations.
where t is the absolute tolerance (as above), and
a
t is the relative tolerance (some make the rela- topological space A pair (X, τ(X)) where
r
tive deviation depend on u as well as on v, such
X is a set and τ(X) its topology. Different
as the sum of magnitudes, |u|+|v|). Almost
choices of the topology τ(X) of a space X corre-
every MPS has a tolerance for every action it
spond to different topological structures on X.
takes during its progression. In particular, one
Examples: If (X, d) is a metric space, then
zero tolerance is not enough. One way to test
we can define U ∈ τ(X) if and only if for all
feasibility is usually one that is used to deter- r
x ∈ U there exists an open ball B ={y ∈ X :
x
mine an acceptable pivot element. In fact, the r
d(x, y) < r} such that x ∈ B ⊂ U ⊂ X. This
x
use of tolerances is a crucial part of an MPS,
is called the metric topology of (X, d).
including any presolve that would fix a variable On any set X we can define the trivial top-
when its upper and lower bounds are sufficiently ology τ(X) ={∅,X} and the discrete topology
close (i.e., within some tolerance). A tolerance in which τ(X) is the set of all subsets of X (so that
is dynamic if it can change during the algorithm. any subset of X is open in the discrete topology).
An example is that a high tolerance might be used
for line search early in an algorithm, reducing it topological transformation A one-to-one
as the sequence gets close to an optimal solu- correspondence between the points of two geo-
tion. The Nelder-Mead simplex method illus- metric figures A and B which is continuous in
trates how tolerances might change up and down both directions. If one figure can be transformed
during the algorithm. into another by a topological transformation,
Another typical tolerance test applies to re- the two figures are said to be topologically
siduals to determine if x is a solution to Ax = b. equivalent.
© 2003 by CRC Press LLC
© 2003 by CRC Press LLC