Pedigree Polytopes: New Insights on Computational Complexity of Combinatorial Optimisation Problems

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