Advances In Combinatorial Optimization: Linear Programming Formulations Of The Traveling Salesman And Other Hard Combinatorial Optimization Problems

Linear Programming Formulations of the Traveling Salesman and Other Hard Combinatorial Optimization Problems

Moustapha Diaby, Mark H Karwan

• Publisher: WSPC
• Year: 2016
• ISBN:
  9789814704892
• Topic: Sciences biologiques
• Subtopic: Science générale

Combinational optimization (CO) is a topic in applied mathematics, decision science and computer science that consists of finding the best solution from a non-exhaustive search. CO is related to disciplines such as computational complexity theory and algorithm theory, and has important applications in fields such as operations research/management science, artificial intelligence, machine learning, and software engineering.

Advances in Combinatorial Optimization presents a generalized framework for formulating hard combinatorial optimization problems (COPs) as polynomial sized linear programs. Though developed based on the 'traveling salesman problem' (TSP), the framework allows for the formulating of many of the well-known NP-Complete COPs directly (without the need to reduce them to other COPs) as linear programs, and demonstrates the same for three other problems (e.g. the 'vertex coloring problem' (VCP)). This work also represents a proof of the equality of the complexity classes "P" (polynomial time) and "NP" (nondeterministic polynomial time), and makes a contribution to the theory and application of 'extended formulations' (EFs).

On a whole, Advances in Combinatorial Optimization offers new modeling and solution perspectives which will be useful to professionals, graduate students and researchers who are either involved in routing, scheduling and sequencing decision-making in particular, or in dealing with the theory of computing in general.

Combinational optimization (CO) is a topic in applied mathematics, decision science and computer science that consists of finding the best solution from a non-exhaustive search. CO is related to disciplines such as computational complexity theory and algorithm theory, and has important applications in fields such as operations research/management science, artificial intelligence, machine learning, and software engineering.

Advances in Combinatorial Optimization presents a generalized framework for formulating hard combinatorial optimization problems (COPs) as polynomial sized linear programs. Though developed based on the 'traveling salesman problem' (TSP), the framework allows for the formulating of many of the well-known NP-Complete COPs directly (without the need to reduce them to other COPs) as linear programs, and demonstrates the same for three other problems (e.g. the 'vertex coloring problem' (VCP)). This work also represents a proof of the equality of the complexity classes "P" (polynomial time) and "NP" (nondeterministic polynomial time), and makes a contribution to the theory and application of 'extended formulations' (EFs).

On a whole, Advances in Combinatorial Optimization offers new modeling and solution perspectives which will be useful to professionals, graduate students and researchers who are either involved in routing, scheduling and sequencing decision-making in particular, or in dealing with the theory of computing in general.

Readership: Professionals, graduate students and researchers who are either involved in routing, scheduling and sequencing decision-making in particular, or in dealing with the theory of computing in general.
Key Features:

• The book offers a new proof of the equality of the complexity classes "P" and "NP"
• Although our approach is developed using the framework of the TSP, it has natural analogs for the other problems in the NP-Complete class thus providing a unified framework for modeling many combinatorial optimization problems (COPs)
• The book makes a contribution to the theory and application of Extended Formulations (EFs) refining the notion of EFs by separating the case in which that notion is degenerate from the case in which the notion of EF is well defined/meaningful. It separates the case in which the addition of redundant constraints and variables (for the purpose of establishing EF relations) matters from the case in which the addition of redundant constraints and variables does not matter

Chapter 1

Introduction

1. Overview

In this book, we present a generalized framework for formulating hard combinatorial optimization problems (COPs) as polynomial-sized linear programs. The perspective adopted is a substantial departure from the traditional ones that have been used. It rests upon our realization that many of the well-known hard COPs (starting with the Traveling Salesman Problem (TSP)) can be modeled as Assignment Problems (APs) with side/complicating constraints (as described in Chapters 4 and 7). Our overall idea is to use a flow perspective over an AP-based graph. The novel feature in our modeling is that our variables represent “joint flows” on doublets and triplets of arcs of this graph. Hence, in essence, enough information is “built” into the variables themselves that the enforcement of the “complicating constraints” can be done implicitly (in essence; by simply setting appropriate variables to zero). A general sense of the idea may be gained by considering the standard AP/Bipartite Matching Problem (BMP). A graphical illustration of the traditional integer programming (IP)/linear programming (LP) modeling perspective for this problem is illustrated in Figure 1.1. The fact that each node in this graph is isolated reflects what we refer to as a “memorylessness” feature in the traditional IP/LP modeling of this problem. By “memorylessness” we are not referring to independence properties such as often used in probability theory or dynamic programming contexts for example. Rather, we are referring to the fact that knowledge of a particular assignment decision provides no information about the remaining decisions. In the case of the TSP, this refers to the fact that the decision made at a given stage of travel (i.e., the value of a given variable/node) in the traditional IP modeling approach) basically provides no information about the decision made at any of the other stages of travel. In other words, in the case of the TSP, the “memorylessness” we mean refers, literally, to the traveler not remembering which cities he/she has already visited while in the process of deciding which city to visit next (which could result in subtours in his/her overall travel).

Figure 1.1. Modeling variables in the traditional IP modeling approach.

The “memorylessness” described above in relation to Figure 1.1 can be remedied to some extent by using arcs to represent the decision variables, as illustrated in Figure 1.2. For example, if the problem context called for precluding decision “x_1,3” (in Figure 1.1) from being made if decision, say “x_2,2”, has been made (and vice versa), this “complicating” requirement could be implicitly enforced (i.e., without the need for an explicit constraint) in the model based on Figure 1.2, by simply not having an arc linking nodes “x_2,2” and “x_1,3” of Figure 1.2, whereas it would require an explicit constraint in the traditional formulation approach based on Figure 1.1. We will later see that in Figure 1.2, a desired solution (a tour, in the case of the TSP) would be one unit of flow “traveling” through the network in a connected manner from “stage” r = 1 to “stage” r = n with no “level”, i, repeated. Our breakthrough is in the finding that by using variables representing triplets of arcs (not necessarily connected), it is possible to formulate a model whose feasible set consists of points corresponding to convex combinations of such desired solutions only.

Figure 1.2. Improved choice of decision variables.

As far as we know, the first well-publicized attempt at formulating the TSP as a polynomial-sized LP is that of Swart (1986/1987). Not having/having had access to Swart’s paper, we do not know the specifics of his model. However, the widely accepted view is that its non-validity was proved by Yannakakis (1991). The developments in Yannakakis (1991) are based on the stipulations that an LP model under consideration be symmetric and also project to the conventional TSP polytope. More recently, Fiorini et al. (2011; 2012) have removed the stipulation of symmetry. However, their developments still require that a model under consideration project to the conventional TSP polytope. In Chapters 5–6, we provide detailed reasons why the developments in Yannakakis (1991), and Fiorini et al. (2011; 2012), respectively, are not applicable to our proposed model. Specifically, we show that our basic (TSP) model: (1) is non-symmetric; (2) cannot be extended into a symmetric model using the two-indexed (city-to-city) variables that are traditionally used in defining the conventional (“standard”) TSP polytope; (3) does not project to the conventional TSP polytope in a well-defined/non-ambiguous and non-degenerate/meaningful sense; (4) cannot be extended into (and hence, cannot lead to) a polytope which projects to the conventional TSP polytope in a well-defined/non-ambiguous and non-degenerate/meaningful sense. A shorter version of the material developed in Chapter 6 is also available in Diaby and Karwan (2015).

We know of three reports (by the same author) with negative claims which have been publicized having some relation to the modeling approach used in this book. There is a counter-example claim in Hofman (2006) which has to do with the relaxation of the model in Diaby (2006b) suggested in Diaby (2006a, p. 20, “Proposition 6”). There is another counter-example claim (Hofman (2008)) which pertains to a simplification of the model in Diaby (2007) discussed in Diaby (2008). Indeed, further checking revealed that each of the two relaxed models in question (i.e., Diaby (2006a), Diaby (2008)) does reduce to a model from which the variables representing the triplets of “travel legs” can be eliminated, and that there were flawed developments in both of the papers concerned (specifically, “Proposition 6” for Diaby (2006a), and Theorem 25 and Corollary 26 for Diaby (2008)). However, these flaws are not applicable to the published, peer-reviewed papers dealing with the “full” models (Diaby (2006b; 2007)). Hence, the counter-example claims may have had some merit, but they are applicable to the relaxations to which they pertain only. In the appendix to this book, we give complete details on the reasons why the model from which the variables representing triplets of “travel legs” are relaxed does not work, and why the proof logic used in this book (Chapter 3) cannot be applied to that model. The third claim of Hofman (Hofman (2...

Table of contents

• Cover
• Halftitle
• Title
• Copyright
• Contents
• About of Authors
• Preface
• Acknowledgments
• Chapter 1. Introduction
• Chapter 2. Basic IP Model Using the TSP
• Chapter 3. Basic LP Model Using the TSP
• Chapter 4. Generic LP Modeling for COPs
• Chapter 5. Non-Symmetry of the Basic (TSP) Model
• Chapter 6. Non-Applicability of Extended Formulations Theory
• Chapter 7. Illustrations for Other NP-Complete COPs
• Chapter 8. Conclusions
• Bibliography
• Appendix A. On the (Two) Counter-Example Claims