# All Pages

### From Glossary

TNP rule |

See degeneracy graph.

Table constraint |

Tableau |

(pl. *tableaux*). A detached coefficient form of a system of equations, which can change from
to
The primes denote changes caused by multiplying the first equation system by the basis inverse (a sequence of pivots in the simplex method). Although the exact form varies (e.g., where to put ), the following is fairly standard:

Nonbasic Variables | |||||
---|---|---|---|---|---|

Basic Variables | Basic Level | at lower bound | at upper bound | | | superbasic |

name (or index) | coefficients are negatives of the rates of substitution | ||||

obj | reduced costs | | | Lagrange multiplier | ||

(Other information could be appended, such as the original bound values.)

Tabu search |

This is a metaheuristic to solve global optimization problems, notably combinatorial programs, based on multi-level memory management and response exploration. It requires the concept of a neighborhood for a trial solution (perhaps partial). In its simplest form, a tabu search appears as follows:

*Initialize*. Select and set*Tabu List*= null. If is feasible, set and otherwise, set (for minimization set ).*Select move*. Let = set of neighbors of If is empty, go to update. Otherwise, select where E is an*evaluator function*that measures the merit of a point (need not be the original objective function, ). If y is feasible and set and Set (i.e., move to the new point).*Update*. If some stopping rule holds, stop. Otherwise, update (by some*tabu update rule*) and return to select move.

There are many variations, such as *aspiration levels*, that can be included in more complex specifications.

Tangent cone |

Let
and let
The *tangent cone*,
is the set of points that have the following limit properties:
is in
if there exist sequences
such that
This arises in connection with the Lagrange Multiplier Rule much like
the tangent plane, though it allows
for more general constraints – e.g., set constraints. In
particular, when there are only equality constraints,
of
if
has full row rank.
(There are some subtleties that render the tangent cone more
general, in some sense, than the tangent plane or null space. It is
used in establishing a *necessary* constraint qualification.)

Tangent plane |

Consider the surface,
where
A *differentiable curve* passing thru
is
for which the derivative, exists, where The *tangent plane* at is the set of all initial derivatives: (This is a misnomer, except in the special case of one function and two variables at a non-stationary point.) An important fact that underlies the classical Lagrange multiplier theorem when the rank of
is full row ( is then called a *regular point*): the tangent plane is

Extending this to allow inequalities, the equivalent of the tangent plane for a regular point is the set of directions that satisfy first-order conditions to be feasible:

Target analysis |

This is a metaheuristic to solve global optimization problems, notably combinatorial programs, using a *learning mechanism*. In particular, consider a branch and bound strategy with multiple criteria for branch selection. After solving training problems, hindsight is used to eliminate
dead paths on the search tree by changing the weights on the criteria: set such that
at node with value,
that begins a dead path, and
at each node, i, on the path to the solution. If such weights exist, they define a separating hyperplane for the test problems. If such weights do not exist, problems are partitioned into classes, using a form of *feature* analysis, such that each class has such weights for those test problems in the class. After training is complete, and a new problem arrives, it is first classified, then those weights are
used in the branch selection.

Taylor expansion |

For
Taylor's Theorem is used by dropping the remainder term. The *first-order expansion* is
and the *second-order expansion* is

(See Myths and Counter Examples in Mathematical Programming to avoid misconception.)

Taylor series |

For a function, having all derivatives, the series is:

where is the *k*-th derivative of Truncating the series at the *n*-th term, the error is given by:

This is a Taylor expansion, and for the Taylor series to equal the functional value, it is necessary that the error term approaches zero for each *n*:

In that case, there must exist in the line segment such that

Taylor theorem |

Then, for

where called the *remainder*, is given by the
integral:

This extends to multivariate functions and is a cornerstone theorem in nonlinear programming. Unfortunately, it is often misapplied as an approximation by dropping the remainder, assuming that it goes to zero as (See
Myths and Counter Examples in Mathematical Programming to avoid misconception.)

Temporal CSP |

A temporal constraint satisfaction problem (TCSP) is a constraint satisfaction problem that involves a set of variables having continuous or discrete domains; each variable represents a time point. Each constraint is represented by a set of intervals .

A unary constraint restricts the domain of variable to the given set of intervals; that is, it represents the disjunction .

A binary constraint restricts the permissible values for the distance ; it represents the disjunction .

In canonical form, all intervals of a constraint are pair-wise disjoint.

Theorem of alternative |

One that establishes two systems are alternatives.

Tight constraint |

Same as active constraint, but some authors exclude the redundant case, where an inequality constraint happens to hold with equality, but it is not binding.

Time staged |

A model with a discrete time parameter, as in dynamic programming, but the solution technique need not use the DP recursion. The number of time periods is called the *planning horizon*.

Tolerance approach |

This is an approach to sensitivity analysis in linear programming that expresses the common range that parameters can change while preserving the character of the solution. In particular, suppose is an optimal basis and rim data changes by The tolerance for this is the maximum value of for which remains optimal as long as for all and for all The tolerance for the basis, can be computed by simple linear algebra, using tableau information.

Tolerances |

Small positive values to control elements of a computer implementation of an algorithm. When
determining whether a value, is non-negative, the actual test is where is an *absolute tolerance*. When comparing two values to determine if the actual test is

where is the absolute tolerance (as above), and is the *relative tolerance* (some make the relative deviation depend on as well as on such as the sum of magnitudes,
). Most MPSs have a tolerance for every action it takes during its progression; in particular, one zero tolerance is not enough - one to test feasibility is usually less than one that is used to determine an acceptable pivot element. In fact, the use of tolerances is a crucial part of an MPS, including any presolve that would fix a variable when its upper and lower bounds are "sufficiently close" (i.e., within some tolerance). A tolerance is *dynamic* if it can change during the algorithm. An example is that a high tolerance might be used for line search early in an algorithm, reducing it as the sequence gets close to an optimal solution. The Nelder-Mead simplex method illustrates how tolerances might change up and down during the algorithm.

Another typical tolerance test applies to residuals to determine if is a solution to In this case, the residal is and the test has the form:

where is some norm. Further details are in the note on Tolerances.

Topological sort |

This sorts the nodes in a network such that each arc, say k-th, has in the renumbered node indexes. This arises in a variety of combinatorial programs, such as those with precedence constraints. If the nodes cannot be topologically sorted, the network does not represent a partially ordered set. This means, for example, there is an inconsistency in the constraints, such as jobs that cannot be sequenced to satisfy the asserted precedence relations.

Totally unimodular matrix |

See unimodular matrix.

Transportation problem |

Find a flow of least cost that ships from supply sources to consumer destinations. This is a bipartite network, , where is the set of sources, is the set of destinations, and is the set of arcs. In the standard form, is bi-complete (A contains all arcs from to ), but in practice networks tend to be sparsely linked. Let be the unit cost of flow from to = supply at i-th source, and = demand at j-th destination. Then, the problem is the linear program:

The decision variables are called *flows*, and the two classes of constraints are called *supply limits* and *demand requirements*, resp. (Some authors use equality constraints, rather than than the inequalities shown.) An extension is the *capacitated transportation problem*, where the flows have bounds:

Transposition theorem |

Same as a theorem of the alternative.

Transshipment problem |

This is an extension of the transportation problem whereby the network is not bipartite. Additional nodes serve as transshipment points, rather than provide supply or final consumption. The network is N = [V, A], where V is an arbitrary set of nodes, except that it contains a non-empty subset of supply nodes (where there is external supply) and a nonempty subset of demand nodes (where there is external demand). A is an arbitrary set of arcs, and there could also be capacity constraints.

Traveling salesman problem |

Given points and a cost matrix, a *tour* is a permutation of the points. The points can be cities, and the permutation the visitation of each city exactly once, then returning to the first city (called *home*). The cost of a tour, is the sum of its costs:

where is a permutation of The TSP is to find a tour of minimum total cost. The two common integer programming formulations are:

- ILP:

*Subtour elimination constraints:*

- where

- QAP:

- where

In each formulation, is the assignment polytope. The *subtour elimination constraints* in ILP eliminate assignments that create cycles, such as shown in the following figure:

The first subtour is eliminated by which requires The second subtour is eliminated by which requires

In ILP, it is easy to incorporate missing arcs: replace the subscripts with an arc index, Then, the subtour elimination constraints have sums over arcs whose head is in The quadratic assignment problem formulation (QAP) is well suited to certain solution methods, such as neural networks.

When the cost matrix is symmetric, it is called the *symmetric* TSP. When the points are in the plane, and the cost matrix is the Euclidean distance matrix, it is called the
*Euclidean* TSP. See the *n*-Opt heuristic.

Triangle inequality |

A property of a distance function:

Triangular matrix |

A square matrix, is called *upper triangular* if all elements are zero below the main diagonal -- i.e.,
It is called *lower triangular* if its transpose is upper triangular. We sometimes call a matrix *triangular* if it is either lower or upper triangular.

Trim problem |

Truncated gradient |

Projection of the gradient of a function, on a box, to put zeroes in coordinates if the sign of the partial derivative is negative at the lower bound or it is positive at the upper bound. This yields a feasible direction, but it does not converge due to the zig-zag phenomenon.

Trust region method |

The iteration is defined as , where is the (complete) change determined by a subproblem of the form:

where F depends on the iterate and is an approximation of the change in objective function value. The particular norm and the magnitude of D determine the set of admissible change values (p), and this is called the *trust region*. A common choice of F is the quadratic form using the Taylor expansion about the current iterate, x, as:

Using the Euclidean norm and applying the Lagrange Multiplier Rule to the subproblem yields p from the equation:

Note that for u=0, the iteration is Newton's method, and for
very large u, the iteration is nearly Cauchy's steepest ascent.

Categories: Linear Programming | Constraint Programming | Linear Programming | MIP/CO | Nonlinear Programming | MIP/CO | Nonlinear Programming | Constraint Programming | Linear Programming | Linear Programming | Linear Programming | MIP/CO | MIP/CO | Common Problems | Linear Programming | Linear Programming | Common Problems | Linear Programming | Common Problems | MIP/CO | Linear Algebra & Geometry | Linear Programming | MIP/CO | Nonlinear Programming | Nonlinear Programming