Overview/Purpose
- The purpose of this computational challenge is to engage the research community.
- The authors will pay a $10,000 (US) prize to the first researcher or group of researchers who offers a counter-example to their linear programming model for solving for the TSP and QAP.
- The resources and conditions of the challenge are described below.
Resources
- Paper:
Exact extended formulation of the linear assignment problem (LAP) polytope for solving the traveling salesman and quadratic assignment problems. In this paper, you can find the linear programming formulation for TSP or QAP. - C# Computer Codes: Basic version and Extended version.
Sample codes provide examples to build the model with CPLEX and solve it. The .Net versions have a user-friendly UI to change experiment parameters, while the .Net Core versions are small versions with the model formulation only. You are welcome to use them directly or program in your own way to test. The “extended” versions of the computer codes include the redundant constraints which are added in order to mitigate numerical stability issues as described in section 6 of the paper above.
Timeframe
The challenge is closed until further notice, while we evaluate a submission we have received.
How to win
- The submission must be received by one of the co-authors. The receipt time is based on the email system time.
- The submission must be a specific TSP or QAP instance.
- If the submission is a TSP instance. The cost matrix file should be included, following the sample xml or csv format. (Click the links to download sample data files.)
- If the submission is a QAP instance. The cost, distance and flow matrix file should be included, following the sample csv format. (Click the link to download sample data file.)
- The submission must include the optimal objective value and solution details, i.e. routes for TSP, or, assignments for QAP. With this information, the optimal objective value and feasibility to all constraints is able to be validated.
- The submission must include the optimal solution obtained by our LP model claimed. This solution will be validated by the authors using one of the well-established commercial LP solvers, such as CPLEX, GUROBI, etc. In order to win the prize, this claimed optimal objective value of the LP model should be NOT equal to the actual optimal solution of the submitted problem instance, i.e. the value of the claimed counter-example. A failure due to numerical difficulties of computers is not considered to be a counter-example. See the next section for more clarification on this and for additional considerations.
Additional Clarifications & Considerations
- Due to the accuracy tolerance of commercial solvers and computers, the objective value of LP models could have a small gap from the actual one, for example 10 vs 9.9999998. Sometimes, the gap could be as big as 0.0001 (or others). In such a case, you should be very careful to judge whether the gap is due to computer accuracy or model incorrectness. We give a brief overview of the specifics we encountered under the “Numerical Issues” tab of this website. An issue attributable to numerical issues (for example, numerical stability and round-off errors) will not be considered as a basis for a valid claim of a counter-example.
- When multiple optimal solutions exist, some LP algorithms, e.g. an interior point method, may terminate with a non-extreme point solution. In such a case, the solution would be a convex combination of multiple optimal solutions. Thus, in such a case for the TSP for example, the optimal route may not be straightforward to identify, even though the optimal objective value would be equal to the optimal TSP tour cost. Hence, in this challenge, one only needs to compare the objective value of the LP model to that of the provided IP benchmark (which is also provided in the code) in order to decide whether or not a counter-example has been found.
- The “extended” version of our code has been consistently robust in all of our experimentations. Hence, it provides a recourse in case of numerical difficulties, although this cannot be guaranteed, due to the fact that the “extension” consists of adding redundant constraints only, as described in the paper.
- The task of comparing the optimal LP and IP benchmark values is easiest if all costs are integer. However, this is not required.