Counter-Example to Diaby’s et al. Linear Programming Solution to the Traveling Salesman Problem

Radosław Hofman and Abdellatif Ben Makhlouf

Complexity, 2025, vol. 2025, 1-14

Abstract: This article presents a method of constructing counter-examples and a complete counter-example to the linear programming model alleged to be the solution to the traveling salesman problem. The counter-example is checked against the model proposed by Diaby et al. However, it applies to all similar formulations of the TSP problem.Although the model in question was published in 2006, and there were several discussions regarding its correctness, the counter-example was never presented.The presented counter-example is a regular graph, and the aim was not to have an example with the least possible size; therefore, the focus was on clarity. The counter-example has, therefore, 366 nodes in two main clusters, each node (in the main part) having exactly four connections to other nodes in the cluster.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/complexity/2025/3672180.pdf (application/pdf)
http://downloads.hindawi.com/journals/complexity/2025/3672180.xml (application/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:complx:3672180

DOI: 10.1155/cplx/3672180

Access Statistics for this article

More articles in Complexity from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().