This book defines and studies a combinatorial object called the pedigree and develops the theory for optimising a linear function over the convex hull of pedigrees (the Pedigree polytope). A strongly polynomial algorithm implementing the framework given in the book for checking membership in the pedigree polytope is a major contribution.
This book challenges the popularly held belief in computer science that a problem included in the NP-complete class may not have a polynomial algorithm to solve. By showing STSP has a polynomial algorithm, this book settles the P vs NP question.
This book has illustrative examples, figures, and easily accessible proofs for showing this unexpected result. This book introduces novel constructions and ideas previously not used in the literature. Another interesting feature of this book is it uses basic max-flow and linear multicommodity flow algorithms and concepts in these proofs establishing efficient membership checking for the pedigree polytope. Chapters 3-7 can be adopted to give a course on Efficient Combinatorial Optimization. This book is the culmination of the author's research that started in 1982 through a presentation on a new formulation of STSP at the XIth International Symposium on Mathematical Programming at Bonn.
Author(s): Tirukkattuppalli Subramanyam Arthanari
Publisher: Springer
Year: 2023
Language: English
Pages: 234
City: Singapore
Preface
Acknowledgments
Epigraph
Mathematics as seen by the poet
Contents
Abbreviations
Acronyms
Symbols
List of Figures
List of Tables
1 Prologue
1.1 Prelude to a New Beginning
1.1.1 What Are Combinatorial Optimisation Problems?
1.2 Languages, Decision Problems, Algorithms, A-Machines
1.3 A New Beginning
1.3.1 How Hard Is the Symmetric Travelling Salesman Problem?
1.3.2 What Are Pedigrees?
1.4 Insightful Strategies and Inexpensive Slingshots
1.4.1 Tools from Past, Slingshots for Attack
1.5 Strategies for Avoiding Non-determinism
1.6 Structure of the Book
1.6.1 Pathways to Read the Book
2 Notations, Definitions and Briefs
2.1 Basic Notations
2.2 Graph Theory
2.3 Convex Sets, Polytopes
2.4 Linear Programming
2.5 Flows in Networks
2.5.1 FAT Problem, Rigid, Dummy Arcs
2.5.2 Two Partitions and a FAT Problem
2.6 0/1-Polytopes
2.6.1 Some Properties of 0/1 Polytopes
2.6.2 New Results on Simplex Method for 0/1 LP
2.7 Appendix on Frozen Flow Finding Algorithm
3 Motivation for Studying Pedigrees
3.1 Notations and Definitions
3.2 A 0/1 Programming Formulation of the STSP: MI-Formulation
3.3 Properties of MI-Formulation
3.4 MI-Relaxation Polytope and Subtour Elimination Polytope
3.4.1 What Next?
4 Structure of the Pedigree Polytope
4.1 Introduction
4.2 MI-Relaxation Polytope
4.3 A Polytope That Contains Pedigree Polytope
4.3.1 Alternative Definition of a Pedigree
4.4 Characterisation Theorems
4.5 Nonadjacency in Pedigree Polytopes
4.5.1 FAT Problems and Adjacency in Pedigree Polytope
4.5.2 Graph of Rigidity and Its Implications
4.5.3 Characterisation of Nonadjacency Through the Graph of Rigidity
4.5.4 Adjacency in Pedigree Polytope Does Not Imply Adjacency in Tour Polytope
4.6 Nonadjacency in Pedigree Polytope Implies Nonadjacency in Tour Polytope
4.6.1 Pedigree Polytope is a Combinatorial Polytope
4.6.2 Diameter of the Pedigree Polytope and Related Results
4.6.3 What Next?
5 Membership Checking in Pedigree Polytopes
5.1 Introduction
5.2 Construction of the Layered Network
5.2.1 Construction of the Network for k = 4
5.2.2 Overview of the Membership Checking in Pedigree Polytope
5.3 Construction of the Layered Network for k > 4
5.3.1 Capacity Along a Link
5.3.2 Completing the Construction of the Layered Network
5.4 A Sufficient Condition for Non-membership
5.4.1 Pedigree Packability of Arc Flows
5.5 A Multicommodity Flow Problem to Check Membership
5.5.1 Defining the Multicommodity Flow Problem
5.5.2 Proving the Necessity of the Condition
5.5.3 Proving the Sufficiency of the Condition
6 Computational Complexity of Membership Checking
6.1 Computational Complexity of Checking the Necessary and Sufficient Condition
6.1.1 On the Mutual Adjacency of Pedigrees in the Set of Rigid Pedigrees
6.1.2 Estimating the Computational Burden at Different Steps of the Framework
6.2 Concluding Remarks
6.3 Appendix: Illustrative Example
7 Efficient Checking of Membership in Pedigree Polytope and Its Implications
7.1 Introduction
7.2 Polytopes and Efficiency
7.3 Membership and Optimisation
7.3.1 Dimension of the Pedigree Polytope
7.4 Conclusion
7.5 Appendix: Excerpts from Maurras's Separation Construction for a Polytope
7.5.1 Construction and Its Validity
8 Epilogue
8.1 Introduction
8.2 Comparison of Different Formulations of STSP
8.2.1 Hypergraph and Flows
8.2.2 Lagrangian Relaxation and Variants
8.2.3 Leontief Substitution Flow Problems
8.3 MI-Relaxation and Leontief Substitution Flow Problem
8.3.1 Lagrangian Relaxation of Multiple Choice Constraints
8.3.2 Value Iteration Algorithm for Problem8.3
8.3.3 Lagrangian Dual of Problem8.2: LD
8.4 Hypergraph Flow and MI-Relaxation
8.5 Clever Methods of Exhaustion: Relaxations for the TSP
8.5.1 Branching Methods
8.6 Branch and Bound Method for MI Formulation
8.7 Conclusion
8.8 Appendices
8.8.1 Appendix 1: On Branch & Bound Computational Comparisons
8.8.2 Appendix 2: On Computational Comparisons
8.8.3 Appendix 3: On the Specialised Version of the Procedure FLOW
Appendix Bibliographical Notes
Chapter 1摥映數爠eflinkchapter111
Chapter 2摥映數爠eflinkchapter222
Chapter 3摥映數爠eflinkchapter333
Chapter 4摥映數爠eflinkchapter444
Chapter 5摥映數爠eflinkchapter555
Chapter 6摥映數爠eflinkchapter666
Chapter 7摥映數爠eflinkchapter777
Chapter 8摥映數爠eflinkchapter888
Appendix References
Index
