A Multi-Commodity Flow Linear Programming with Polynomial Constraints for Black and White Traveling Salesman Problem

The black and white salesman problem (BWTSP) is a new NP-hard problem, which can be divided into the undirected BWTSP and the directed BWTSP according to the symmetry of edges in graph. As a basis of complete algorithm design for NP-hard problems, the number of constraints in linear programming (LP) remarkably influences the complexity of algorithm design. The existing Ghiani LP for the undirected BWTSP contains an exponential number of constraints. For a special case of the direct BWTSP whose L=+∞, its LP with polynomial constraints can be obtained by being transformed into RATSP. However, there exists no LP for the general directed BWTSP. A new LP with polynomial constraints for the directed BWTSP is proposed. Firstly, the directed BWTSP is reduced to ATSP whenever Q=L=+∞. Then, based on the Finke-Claus-Gunn LP with n(n+4) constraints of ATSP, the n\+2+2|W| cardinality constraints can be acquired by defining residual and used cardinality commodity flow. Finally, the new n\+2+n+2|B| weight constraints are obtained by similar ways. In this way, the new LP with 3n\+2+7n constraints only can be eventually acquired. Since the undirected BWTSP and the directed BWTSP with L=+∞ are both special cases of the directed BWTSP, the results can be applicable to them too.