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

MaRDI QIDQ1101340zbMATH OpenFDO

Authors Rick Greer

Publication date 1984

Published in Annals of Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

functions of systems of linear relationspolyhedral convex conestree algorithm

Mathematics Subject Classification ID

Polytopes and polyhedra (52Bxx) Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Linear programming (90C05)

Review text

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.

Recommendations

• An O(n^ 2) simplex algorithm for a class of linear programs with tree structure
• A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs
• scientific article; zbMATH DE number 4083392
• scientific article; zbMATH DE number 203962
• scientific article; zbMATH DE number 4066615

Cited in

(12)

• An O(n^ 2) simplex algorithm for a class of linear programs with tree structure
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• The MIN PFS problem and piecewise linear model estimation
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• On highly robust efficient solutions to uncertain multiobjective linear programs
• Nonlinear desirability as a linear classification problem
• Maximum feasible subsystems of distance geometry constraints
• On linear operators preserving certain cones in \(\mathbb{R}^n\)
• scientific article; zbMATH DE number 4020870 (Why is no real title available?)
• A Benson-type algorithm for bounded convex vector optimization problems with vertex selection
• On minimal positive basis for polyhedral cones in Rn
• On the B-differential of the componentwise minimum of two affine vector functions

This page was built for publication: Trees and hills: methodology for maximizing functions of systems of linear relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1101340)