TSPLPSolver - coin-or-foundation/tlc GitHub Wiki

Contribution Review Checklist for TSP LP Solver

General

  • Project Description: TSP LP Solver is a program to build linear programming models for the traveling salesman problem and solve it based on CPLEX and C#.NET.
  • Contributor: Lei Sun ([email protected])
  • Contact Date: 26th February 2016
  • Handler: Stefan Vigerske
  • Reviewer: D.S. (see review below)
  • Sent instructions to reviewer: 29th February 2016

Legal

  • Received CSRO: 10th February 2016
  • Received DOL: 10th February 2016
  • OSI-approved license: EPL

Accepted

  • No: 19th March 2016

Comment by submission handler: I follow the reviewers suggestion to reject the model. Next to his experiments, I also tried solving a seemingly small instance from TSPLIB with the submitted software. When loading the "48 capitals of the US" tour (att48) in XML format into TSP LP Solver, the application run out of memory while generating the LP model. As a 32bit application, the program must have 3-4 GB of memory available. Trying the instance in TSP file format with concorde, it is solved in 0.10 seconds.

Classification

  • Classified (Level 1-5): (see ProjectCategories)

Code and Documentation

  • README/LICENSE files: (exists and reasonable) (date checked)
  • Project Roadmap (Level 1 only): (exists and reasonable) (date checked)
  • AUTHORS/INSTALL files (Level 2 and above): (exists and reasonable) (date checked)
  • Code builds (Level 2 and above): (date checked)
  • Documentation (Level 3 and above): (exists and reasonable) (date checked)
  • Unit test (Level 4 and above): (has one and passed) (date checked)
  • Project binaries (Level 5): (exist and function properly) (date checked)

Establishing Project

  • PM named: (name) (date)
  • PM familiar with Guidelines and Procedures for Project Management: (date)
    • Legal issues
    • Tracking contributions
    • Responding to bugs
    • Using SVN
    • Using Trac
    • Setting up a static Web page
    • Standard practices (versioning and release, build procedures)
  • Parameters for project creation mailed to submission manager:
   # SVNPROJ  : the project's name in the SVN repository
   # PROJDESC : short project description
   # PM       : space separated list of project manager COIN-OR id's
   # PM_EMAIL : email address of the PM managing the mailing lists

  • PM subscribed to mailing list: (date)

  • Code imported: (date)

  • PM given write access: (date)

  • Trac page set up: (date)

  • XML page (projDesc.xml, see documentation in the file itself, which can be copied and adapted from here) set up: (date)

  • Project listed on projects list, with link to XML file, should happen automatically: (date)

    Old howto:

    • Check out svn repo CoinWeb/projects.
    • Read projects.csv into your favourite spreadsheet (or text editor). Add an appropriate line for the new project and write out a revised projects.csv.
    • Run the command project_list_short.pl projects.csv. This'll produce the file index.html.new and modify the file coin-or-projects.xml.
    • Copy (or move) index.html.new to index.html.
    • Finally, commit the modified projects.csv, index.html, and coin-or-projects.xml.

  • Project announcement: (date)

  • PM invited for full membership of COIN-OR (contact coin secretary): (date)

  • Moved this page to ArchivedChecklists: 19th March 2016

Review (by anonymous reviewer)

At the present time I would recommend rejecting this software for a variety of reasons:

  1. The mathematics on which it is based is not accepted by the research community and most likely flawed. The software implements a polynomially sized LP model that is claimed to represent the TSP polytope. The existence of such a model would resolve the famous P ?= NP question in the affirmative. Although this would be a celebrated result, the work of the authors has not been accepted by the research community. Moreover, other researchers have in fact proven that such a model CANNOT exist; see for example the recent paper Exponential Lower Bounds for Polytopes in Combinatorial Optimization. Note that this referenced paper on exponential lower bounds is accepted for publication in the Journal of the ACM (a top tier journal). I would not believe the claim unless I had personally verified their proof, or seen their work published in a top tier journal (See the discussion here: https://www.win.tue.nl/~gwoegi/P-versus-NP.htm ). Note that if they satisfy the community regarding the correctness of their claim, they will be awarded a $1 million prize by the Clay Math Institute: http://www.claymath.org/millennium-problems/p-vs-np-problem

  2. The submitted software is only able to solve instances of tiny size and therefore serves no practical purpose. Even the MTZ IP formulation significantly outperforms their model, and their model grows too large very quickly (their 30 city model took over 2 gigabytes to represent the .lp file). To give an idea of how slow their model (N5LP) is, on a 4 core 3.4GHz workstation I observed the following solution times (using CPLEX 12.6):

    1. 10 city model: MTZ took 0.03 sec, N5LP took 28 sec
    2. 15 city model: MTZ took 0.2 sec, N5LP took 13721 sec
    3. 20 city model: MTZ took 1.5 sec, N5LP (did not terminate after a long time)

  3. This could be seen as an endorsement of this work by the COIN-OR project, which could be an embarrassment for COIN-OR. Although on the tiny instances for which these LPs are tractable, valid integral solutions and thus tours may be found, this is absolutely not a computational verification of the correctness of this model. Even if they verify the correctness of their model on billions of tiny instances (e.g., dozens of cities), this does not establish the correctness in general -- it is certainly possible that their model does capture the TSP polytope for small values of n. If they were able to verify its correctness on even a few or the larger instances in the TSPLIB (for example, instances with 1000+ cities) then this may be more interesting evidence in their favor (but still not a proof). For example, in the computational work of others on the TSP, certain classes of inequalities such as combs and domino parity inequalities do not really come into play until the instances have hundreds of thousands of cities.

  4. If the authors wish to computationally evaluate their model and try to show its effectiveness on larger sized instances they should at the very least implement a constraint generation routine that separates and adds constraints to the model dynamically instead of explicitly adding all constraints to the model (the way it is typically done with subtour inequalities, see “The Traveling Salesman Problem” by Applegate et al.). However, even if they did this, I would still not recommend accepting this software until the mathematical basis of their work is verified.

Based on the above reasons I would therefore recommend that this software project is rejected. I would also recommend that future submissions of a similar nature by the same authors are also rejected until their claim that P=NP is verified and accepted by the computer science research community.

Response to Review (received by M. Kanellos, 5th of April 2019)

I read your rejection of the LP Solver by Lei Sun regarding the really interesting approach for solving the TSP which was introduced by Moustapha Diaby and developed further now several times, see

https://arxiv.org/abs/1610.00353

Until a few years ago I was a firm 'believer' in the P <> NP claim, however to my own surprise this did fundamentally change when I read about the Diaby / Karwan algorithms.

I do think that some proof enhancements are necessary. But since studying the algorithms in detail has become a very interesting 'hobby' of mine - I am sure that they indeed are correct. The correctness proof depends solely on the answer to the question whether the introduced polytopes are integral.

And there are absolutely no hints that this is not the case.

Especially the alleged impossibility claims which you also referred to in your rejection are clearly wrong and intentionally misunderstand the whole matter in a quite obvious way-

See explanations below. It is obvious for anyone who is seriously interested in the TSP algorithm that the Linear Programming model by Diaby, Karwan and Sun is very interesting.

Regards,

Michael Kanellos

EXPLANATIONS / LINKS:

  • The alternate polytope used by Diaby, Karwan and Sun is completely different from the standard TSP polytope and so no mathematical claims or results regarding the standard TSP polytope can be directly applied to the alternate polytope, especially the alternate polytope TSP modelling is not 'symmetric' in the sense of the standard TSP polytope (the handling of the first-and-last city of a TSP solution is indeed the crucial idea)

  • the important notion of extended formulation is intentionally wrongly applied by the authors of the impossibility claims, and this is quite blatant, you see this in https://arxiv.org/abs/1902.03549

Of course not every linear map is a projection, but the authors of the impossibility claims do indeed wrongly "replace" the necessary projection in extended formulations by general linear maps whenever it "suits" them. So the notion of extended formulation becomes completely useless in the impossibility claim. How can this be overlooked by reviewers?

An interesting geometrical proof technique of integrality of the Assignment Problem: http://www.people.vcu.edu/~ghurlbert/papers/SPBVNT.pdf