For the first time, this book unites different algebraic approaches for discrete optimization and operations research. The presentation of some fundamental directions of this new fast developing area shows the wide range of its applicability. Specifically, the book contains contributions in the following fields: semigroup and semiring theory applied to combinatorial and integer programming, network flow theory in ordered algebraic structures, extremal optimization problems, decomposition principles for discrete structures, Boolean methods in graph theory and applications.
Inhaltsverzeichnis
1;Front Cover;1 2;Algebraic and Combinatorial Methods in Operations Research;4 3;Copyright Page;5 4;Contents;8 5;Foreword;6 6;Chapter 1. Packing problems in semigroup programming;12 7;Chapter 2. A greedy algorithm for solving network flow problems in trees;34 8;Chapter 3. A dual optimality criterion for algebraic linear programs;46 9;Chapter 4. On properties of solution sets of extremal linear programs;52 10;Chapter 5. Using fields for semiring computations;66 11;Chapter 6. Scheduling by non-commutative algebra;86 12;Chapter 7. Pseudo-boolean functions and stability of graphs;94 13;Chapter 8. Independence systems and perfect k-matroid-intersections;110 14;Chapter 9. Matroids on ordered sets and the greedy algorithm;126 15;Chapter 10. An algorithm for the unbounded matroid intersection polyhedron;140 16;Chapter 11. Algebraic Flows;146 17;Chapter 12. Linear algebra in dioids: a survey of recent results;158 18;Chapter 13. Algebraic flows and time-cost tradeoff problems;176 19;Chapter 14. Ranking the cuts and cut-sets of a network;194 20;Chapter 15. Shortest paths in signed graphs;212 21;Chapter 16. A boolean algebraic analysis of fire protection;226 22;Chapter 17. Iteration and summability in semirings;240 23;Chapter 18. Substitution decomposition for discrete structures and connections with combinatorial optimization;268 24;Chapter 19. On max-separable optimization problems;368 25;Chapter 20. Minimization of combined objective functions on integral submolar flows;374