Using Gavish-Grave LP to Formulate the Directed Black and White Traveling Salesman Problem

He Jiang, Xianchao Zhang, Mingchu Li, Haoyang CheInternational Conference on Computational Science 2007 · DOI

Abstract

This paper presents the first polynomial-sized Linear Programming (LP) formulation for the directed Black and White Traveling Salesman Problem (BWTSP). By extending the Gavish-Grave model for the Asymmetric Traveling Salesman Problem (ATSP), the authors introduce a novel "flow-based" approach to manage cardinality and length constraints. The resulting model utilizes $3n^2 + 2n$ constraints, providing a significant reduction in complexity compared to previous exponential-sized formulations.

Introduction

The Traveling Salesman Problem (TSP) is a foundational challenge in combinatorial optimization, requiring the identification of the shortest Hamiltonian cycle in a graph. The Black and White TSP (BWTSP) introduces two specific constraints that reflect real-world requirements in telecommunications and logistics. In this variant, vertices are partitioned into two sets: black vertices (representing major hubs or ring offices) and white vertices (representing local nodes).

Two primary constraints govern the BWTSP:

  1. Cardinality Constraints: No more than $Q$ white vertices may be visited between any two consecutive black vertices.
  2. Length Constraints: The total distance traveled between two consecutive black vertices cannot exceed a maximum limit $L$.

These constraints are particularly relevant for designing Synchronous Optical Networking (SONET) fiber rings and optimizing airline schedules. While previous research addressed undirected versions or specific cases where $L$ was infinite, a general, efficient LP formulation for the directed BWTSP remained elusive until this work.

Methodology: The Gavish-Grave Extension

The authors base their formulation on the Gavish-Grave LP, a known model for the Asymmetric TSP (ATSP) that utilizes commodity flow variables to eliminate illegal subtours. To adapt this to the BWTSP, the authors introduce a "refresh" mechanism where black vertices act as replenishment points for specific resources.

Flow Variables

The model incorporates two new types of continuous flow variables to track the state of the tour relative to the $Q$ and $L$ constraints:

  • Cardinality Flow ($q_{ij}$): This variable tracks the remaining quota of white vertices allowed before a black vertex must be reached. When the salesman departs a black vertex, the quota is reset. Each white vertex visited consumes one unit of this quota. If the quota reaches zero before the next black vertex, the path is deemed infeasible.
  • Length Flow ($l_{ij}$): Similar to the cardinality flow, this variable tracks the remaining distance allowed. The distance limit is refreshed at every black vertex and depleted according to the weights of the arcs traversed between white vertices.

By integrating these flows, the authors describe the problem using $n(n-1)$ binary variables and $3n(n-1)$ continuous variables. This results in a total of $3n^2 + 2n$ constraints, ensuring the model remains polynomial in size relative to the number of nodes $n$.

Theoretical Results

The primary contribution of this paper is the proof of mathematical validity for this $O(n^2)$ formulation. Through Propositions 1 and 2, the authors demonstrate that the cardinality and length constraints effectively exclude any tour that violates the $Q$ or $L$ limits.

Furthermore, the authors note that this directed formulation is generalizable. Since an undirected graph can be represented as a directed graph by replacing each edge with two opposing arcs, this LP formulation is also applicable to the undirected BWTSP. This represents a significant improvement over previous undirected models, such as the Ghiani LP, which relied on an exponential number of constraints.

Discussion and Future Work

While the paper establishes a robust mathematical framework, it is primarily theoretical. The authors do not provide empirical data or computational experiments to compare the solving time of this polynomial LP against existing heuristic methods or exponential formulations.

In practice, polynomial size does not always equate to computational speed for NP-hard problems. Future research is required to implement this formulation within Branch-and-Cut or Branch-and-Bound frameworks. Such testing will determine the practical efficiency of the Gavish-Grave extension when applied to large-scale telecommunication and scheduling datasets. Nevertheless, the reduction of the directed BWTSP to a polynomial-sized LP marks a significant milestone in the study of constrained routing problems.

Summary updated

BibTeX
@inproceedings{jiang2007using,
  author = {He Jiang and Xianchao Zhang and Mingchu Li and Haoyang Che},
  title = {{Using Gavish-Grave LP to Formulate the Directed Black and White Traveling Salesman Problem}},
  booktitle = {International Conference on Computational Science},
  year = {2007},
  doi = {10.1007/978-3-540-72588-6\_49},
}
Figure