Advances in Combinatorial Optimization ·Linear Programming Formulations of the Traveling Salesman and Other Hard Combinatorial Optimization Problems by Diaby, Moustapha -- Read -- Imperial Library of Trantor

Index

Cover Halftitle Title Copyright Contents About the Authors Preface Acknowledgments Chapter 1. Introduction

1. Overview 2. Overview of Traditional Formulations of the TSP 3. Basic Notations, Definitions, and Assumptions for the Proposed Modeling

Chapter 2. Basic IP Model Using the TSP

1. Introduction 2. The “Alternate TSP Polytope”: A Non-Exponential Abstraction of TSP Tours 3. “TSP Paths”: Path Representation of TSP Tours 4. Intuition of the LP Modeling of TSP Paths 5. Integer Programming (IP) Model of TSP Paths 6. Structure of the IP Polytope

Chapter 3. Basic LP Model Using the TSP

1. Introduction 2. General Algebraic Characterizations of the LP Polytope 3. “Flow” Structure of the LP Polytope 4. Integrality of the LP Polytope 5. Linear Cost Function for the TSP Paths

Chapter 4. Generic LP Modeling for COPs

1. Introduction 2. Unified Description and Classification of COPs 3. Generic Bipartite Network Flow-Based Model of SCCOP Solutions 4. Generic Flow Graphs (GFG) 5. Overall LP Models for SCCOPs

Chapter 5. Non-Symmetry of the Basic (TSP) Model

1. Introduction 2. Non-Symmetry of the Basic Model 3. Non-Symmetry of “Complexes” of the Basic Model

Chapter 6. Non-Applicability of Extended Formulations Theory

1. Introduction 2. Background Overview 3. Ill-Definition Condition for EFs 4. Redundancy Matters for Polytopes Stated in Independent Spaces

Chapter 7. Illustrations for Other NP-Complete COPs

1. Introduction 2. The Set Partitioning Problem (SPP) 3. The Vertex Coloring Problem 4. The Multiple Traveling Salesman Problem (mTSP)

Chapter 8. Conclusions Bibliography Appendix A. On the (Two) Counter-Example Claims