Zimmermann U. Linear and Combinatorial Optimization in Ordered Algebraic Structures

North-Holland, 1981. — 391 p.The object of this book is to provide an account of results and methods for linear and combinatorial optimization problems over ordered algebraic structures. In linear optimization the set of feasible solutions is described by a system of linear constraints; to a large extent such linear characterizations are known for the set of feasible solutions in combinatorial optimization, too. Minimization of a linear objective function subject to linear constraints is a classical example which belongs to the class of problems considered. In the last thirty years several optimization problems have been discussed which appear to be quite similar. The difference between these problems and classical linear or combinatorial optimization problems lies in a replacement of linear functions over real (integer) numbers by functions which are linear over certain ordered algebraic structures. This interpretation was not apparent from the beginning and many authors discussed and solved such problems without using the inherent similarity to linear and combinatorial optimization problems. Therefore results and methods which are well- known in the theory of linear and combinatorial optimization have been reinvented from time to time in different ordered algebraic structures. In this book we describe algebraic formulations of such problems which make the relationship of similar problems more transparent. Then results and methods in different algebraic settings appear to be instances of general results and methods. Further specializing of general results and methods often leads to new results and methods for a particular problem.
We do not intend to cover all optimization problems which can be treated from this point of view. We prefer to select classes of problems for which such an algebraic approach turns out to be quite useful and for which a common theory has been developed. Therefore nonlinear problems over ordered algebraic structures are not discussed; at the time being very few results on such problems are known.
We assume that the reader of this book is familiar with concepts from classical linear and combinatorial optimization. On the other hand we develop the foundations of the theory of ordered algebraic structures covering all results which are used in the algebraic treatment of linear and combinatorial optimization problems. This first part of the book is self-contained; only some representation theorems are mentioned without explicit proof. These representation theorems are not directly applied in the investigation of the optimization problems considered, but provide a general view of the scope of the underlying algebraic structure. In the second part of the book we develop theoretical concepts and solution methods for linear and combinatorial optimization problems over such ordered algebraic structures. Results from part one are explicitly and implicitly used throughout the discussion of these problems. The following is an outline of the content of the chapters in both parts.Part I: Ordered Algebraic Structures
Ordered Sets, Lattices and Matroids
Ordered Commutative Semigroups
Lattice-Ordered Commutative Groups
Linearly Ordered Commutative Divisor Semigroups
Ordered Semimodules
Linearly Ordered Semimodules over Real Numbers
Part II: Linear Algebraic Optimization
Linear Algebraic Problems
Algebraic Path Problems
Eigenvalue Problems
Extremal linear Programs
Algebraic Linear Programs
Algebraic Flow Problems
Algebraic Independent Set Problems