{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T04:52:58Z","timestamp":1773031978133,"version":"3.50.1"},"reference-count":16,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T00:00:00Z","timestamp":1736294400000},"content-version":"vor","delay-in-days":7,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/doi.wiley.com\/10.1002\/tdm_license_1.1"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Complexity"],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:p>This article presents a method of constructing counter\u2010examples and a complete counter\u2010example to the linear programming model alleged to be the solution to the traveling salesman problem. The counter\u2010example is checked against the model proposed by Diaby et al. However, it applies to all similar formulations of the TSP problem.<\/jats:p>\n                  <jats:p>Although the model in question was published in 2006, and there were several discussions regarding its correctness, the counter\u2010example was never presented.<\/jats:p>\n                  <jats:p>The presented counter\u2010example 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\u2010example has, therefore, 366 nodes in two main clusters, each node (in the main part) having exactly four connections to other nodes in the cluster.<\/jats:p>","DOI":"10.1155\/cplx\/3672180","type":"journal-article","created":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T04:38:56Z","timestamp":1736311136000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Counter\u2010Example to Diaby\u2019s et al. Linear Programming Solution to the Traveling Salesman Problem"],"prefix":"10.1155","volume":"2025","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5693-8151","authenticated-orcid":false,"given":"Rados\u0142aw","family":"Hofman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2025,1,8]]},"reference":[{"key":"e_1_2_9_1_2","doi-asserted-by":"crossref","unstructured":"CookS. A. The Complexity of Theorem-Proving Procedures Proceedings of the Third Annual ACM Symposium on Theory of Computing May 1971 Shaker Heights OH 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_9_2_2","unstructured":"CookS. A. P versus NP Problem http:\/\/www.claymath.org\/millennium\/P_vs_NP\/Official_Problem_Description.pdf."},{"key":"e_1_2_9_3_2","first-page":"745","article-title":"The Traveling Salesman Problem: A Linear Programming Formulation","volume":"6","author":"Diaby M.","year":"2007","journal-title":"WSEAS Transactions on Mathematics"},{"key":"e_1_2_9_4_2","doi-asserted-by":"publisher","DOI":"10.1504\/IJMOR.2017.080739"},{"key":"e_1_2_9_5_2","unstructured":"HofmanR. Report on Article: P\u2009=\u2009NP Linear Programming Formulation of the Traveling Salesman Problem 2006 http:\/\/arxiv.org\/abs\/cs.CC\/0610125."},{"key":"e_1_2_9_6_2","unstructured":"DiabyM. KarwanM. andSunL. On Modeling NP-Complete Problems as Polynomial-Sized Linear Programs: Escaping\/Side-Stepping the Barriers 2023 https:\/\/www.researchgate.net\/publication\/370071460_On_modeling_NP-Complete_problems_as_polynomial-sized_linear_programs_EscapingSide-stepping_the_barriers."},{"key":"e_1_2_9_7_2","unstructured":"DiabyM. P\u2009=\u2009NP: Linear Programming Formulation of the Traveling Salesman Problem 2006 http:\/\/arxiv.org\/abs\/cs.CC\/0609005."},{"key":"e_1_2_9_8_2","unstructured":"DiabyM. KarwanM. andSunL. Exact Extended Formulation of the Linear Assignment Problem (LAP) Polytope for Solving the Traveling Salesman and Quadratic Assignment Problems 2019 https:\/\/www.researchgate.net\/profile\/Moustapha-Diaby-2\/publication\/331113031_Exact_extended_formulation_of_the_linear_assignment_problem_LAP_polytope_for_solving_the_traveling_salesman_and_quadratic_assignment_problems."},{"key":"e_1_2_9_9_2","unstructured":"DiabyM. A O(n8) X O(n7) Linear Programming Model of the Traveling Salesman Problem. Diaby M. Exact Extended Formulation of the Linear Assignment Problem (LAP) Polytope for Solving the Traveling Salesman and Quadratic Assignment Problems Unpublished 2008 https:\/\/arxiv.org\/abs\/0803.4354."},{"key":"e_1_2_9_10_2","unstructured":"HofmanR. Why Linear Programming Cannot Solve Large Instances of NP-Complete Problems in Polynomial Time 2006 https:\/\/arxiv.org\/abs\/cs\/0611008."},{"key":"e_1_2_9_11_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100049811"},{"key":"e_1_2_9_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90042-4"},{"key":"e_1_2_9_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(89)90064-6"},{"key":"e_1_2_9_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/s0095-8956(73)80006-1"},{"key":"e_1_2_9_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s42979-022-01256-0"},{"key":"e_1_2_9_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00219-0"}],"container-title":["Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/cplx\/3672180","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1155\/cplx\/3672180","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/cplx\/3672180","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T03:55:56Z","timestamp":1773028556000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/cplx\/3672180"}},"subtitle":[],"editor":[{"given":"Abdellatif","family":"Ben Makhlouf","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2025,1]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["10.1155\/cplx\/3672180"],"URL":"https:\/\/doi.org\/10.1155\/cplx\/3672180","archive":["Portico"],"relation":{},"ISSN":["1076-2787","1099-0526"],"issn-type":[{"value":"1076-2787","type":"print"},{"value":"1099-0526","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1]]},"assertion":[{"value":"2024-05-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"3672180"}}