The tree algorithm described in this monograph is an algorithm which maximizes functions of systems of linear relations subject to constraints.

Typical problems in this class are concerned with identifying all of those vectors which satisfy or don’t satisfy given linear equalities or inequalities in such patterns as will maximize certain functions of interest. For example, consider the problem of identifying all of those vectors which satisfy as many of an inconsistent system of linear inequalities as possible. For another example, consider two overlapping multidimensional clouds of 0 ’ s and x’s; in this setting, the problem is to determine ail quadratic hypersurfaces which best separate the clouds in the sense of having the fewest number of 0 ’ s on the x side of the surface and vice-versa. Also, as very special cases, this class includes the problems of solving linear programs and systems of linear equations.

The tree algorithm will solve many problems in this class, including all of the ones mentioned above. It is also able to solve problems of this type when the solution vectors are constrained to lie in designated linear manifolds or polyhedral sets or are required to solve other problems of this type.

These problems are typically NP-complete. Existing algorithms for solving problems from this class are essentially complete enumeration algorithms since the order of their time complexity is essentially that associated with enumerating the values of the criterion function on all equivalence classes of vectors. On the other hand, as compared to complete enumeration algorithms, the order of the tree algorithm’s time complexity is geometrically better as the number of variables increases and polynomially better as the number of linear relations increases. Furthermore, as with the complete enumeration algorithms, the tree algorithm will identify a f f solution equivalence classes. Four examples given in this monograph show the tree algorithm to be from 50 to 30,000 times faster than complete enumeration. A fast approximate version of the tree algorithm is seen to be from 6,000 to 55,000 times faster in these examples.
Read more at http://ebookee.org/Trees-and-Hills-Methodology-for-Maximizing-Functions-of-Systems-of-Linear-Relations_237929.html#eq8ZsvmmuW2ebo27.99