Recognition of Gilmore-Gomory traveling salesman problem (Q1080781)

In 1964 Gilmore and Gomory developed an efficient special algorithm for solving the travelling salesman problem of order n with cost matrix \(D=(d_{ij})\) when D is generated by a special procedure. Given are numbers \(A_ i\), \(B_ i\), \(i=1\) to n, and real valued functions defined on \(R^ 1\), f(\(\lambda)\), g(\(\lambda)\), and the distance \(d_{ij}\) is \[ \int^{A_ j}_{B_ i}f(\lambda)d\lambda \quad if\quad A_ j\geq B_ i,\quad or\quad \int^{B_ i}_{A_ j}g(\lambda)d\lambda \quad otherwise. \] The input in the Gilmore-Gomory algorithm are the vectors \(A=(A_ i)\), \(B=(B_ i)\) and the functions f(\(\lambda)\), g(\(\lambda)\). The main question investigated in this paper is the following: Given the cost matrix \(D=(d_{ij})\) only, is it possible to check efficiently whether it is of the Gilmore-Gomory type? The author provides a polynomially bounded algorithm which either establishes that the given matrix D is not of the Gilmore-Gomory type, or generates the vectors \(A=(A_ i)\), \(B=(B_ i)\), and the functions f(\(\lambda)\), g(\(\lambda)\) which yield the matrix D by the Gilmore-Gomory formulas. Two cost matrices \(D'=(d'_{ij})\), \(D''=(d''_{ij})\) for the travelling salesman problem of order n are said to be equivalent if the difference in the cost using the two matrices, is the same constant for all the towers. The author proves that D', D'' are equivalent in this sense iff there exist vectors \(u=(u_ i)\), \(v=(v_ j)\), such that \(d'_{ij}- d''_{ij}=u_ i+v_ j\) for all \(i\neq j.\) Finally we would like to point out an error. Theorem 1 of page 236 about linear programs is wrong as it is stated. The correct statement of this theorem for general linear programs is the following. Let \(K=\{x:\) \(Ex=g\), Fx\(\geq h\}\). cx-c'x is a constant over K iff c-c' is in the linear hull of the set consisting of the row vectors of E, and the row vectors of F corresponding to the binding inequality constraints (i.e., those inequality constraints which hold as equations at all points in K).