Trees and hills: methodology for maximizing functions of systems of linear relations (Q1101340)

This monograph introduces the problem of extremizing functions of systems of linear relations subject to constraints. There are many problems which fall into this category, e.g., the problem of finding solutions to consistent systems of linear inequalities, the linear programming problem, and the problem of finding solutions to systems of linear equations. The author suggests the so-called tree algorithm for solving problems of this class. After having introduced the reader to that part of the theory of polyhedral convex cones which is needed to understand the nature of the tree algorithm (Chapter 2), the author describes a special and then a general version of the tree algorithm and discusses its computational complexity (Chapters 3-6). Chapter 7 is devoted to the comparison of the tree algorithm with other procedures for extremizing functions of systems of linear relations. Various applications of the tree algorithm are surveyed in Chapter 8. Chapter 9 discusses examples of the behaviour of the tree algorithm in practice. The results are summarized in the concluding Chapter 10.