[AlexV]

All your suggestions, complaints and general contest related messages are welcome here.

[Ethatron]

I tried to use the geometric distance function given is the tsplib documentation, but it is wrong somehow. I get shorter routes for ulysees22. All other routes, of varying distance types, are calculated correctly by my solver, so I can only think the doc contains an error.

Anyway, I found a funny way to cheat [yourself]: you have the known best route-lengths of quite some files, abort if it is matched.

Maybe a few questions:
- How much percent of the code has to be AMP?
- Is an exact solver required? Redoing concorde in AMP isn't the task here I think. If not, which is the tolerable limit? Within 99.5% fe.?
- You mention ATSP in the pdfs once, is it necessary to do both? I think it's a bit hard to rank a STSP-only implementation vs. a ATSP-only implementation, which one will it be? (except maybe you calculate FLOPS extracted and use that as rank)
- Can we continue improve while a solution has been send in and the ranking is up? For the DNA-compression contest we were able to beat each other in daily turns. Was a lot of fun and tension, and when the lurkers came up and gave a surprise ... better than cinema.

[AlexV]

Originally Posted by Ethatron

I tried to use the geometric distance function given is the tsplib documentation, but it is wrong somehow. I get shorter routes for ulysees22. All other routes, of varying distance types, are calculated correctly by my solver, so I can only think the doc contains an error.

Anyway, I found a funny way to cheat [yourself]: you have the known best route-lengths of quite some files, abort if it is matched.

Maybe a few questions:
- How much percent of the code has to be AMP?
- Is an exact solver required? Redoing concorde in AMP isn't the task here I think. If not, which is the tolerable limit? Within 99.5% fe.?
- You mention ATSP in the pdfs once, is it necessary to do both? I think it's a bit hard to rank a STSP-only implementation vs. a ATSP-only implementation, which one will it be? (except maybe you calculate FLOPS extracted and use that as rank)
- Can we continue improve while a solution has been send in and the ranking is up? For the DNA-compression contest we were able to beat each other in daily turns. Was a lot of fun and tension, and when the lurkers came up and gave a surprise ... better than cinema.

Well, part of the reason for not disclosing the problem set is to avoid "cheating"...what if the devious goal is to better plan the organizers' shopping routes? Those aren't in TSPLIB We also get to peek at your awesome code during refereeing. On to the questions:
- the solver should be in AMP, possibly intermixed with PPL (heterogeneous FTW);
- depends, both delta from optimal solution and speed to solve factor into the final scoring;
- both symmetrical and asymmetrical cases are factored in, there are algorithms that can deal with both;
- definitely, anyone can submit up to the last minute, and the online ranking will help people to see where they sit.

Hopefully these are a good start with regards to answers - and I hope you join in!

[rapso]

is there some reference framework we could use to jump start? I wouldn't like to be disqualified just due to some wrong interface or something.

could you disclose the complexity of the problems that will need to be solved aka number of nodes?

[AlexV]

Originally Posted by rapso

is there some reference framework we could use to jump start? I wouldn't like to be disqualified just due to some wrong interface or something.

could you disclose the complexity of the problems that will need to be solved aka number of nodes?

A wrong interface wouldn't disqualify you. The code not compiling would disqualify the submission, and use of 3rd party libraries is not accepted, but beyond that we're reasonably lenient, as evidenced in the rules document. There will be a toy-ish implementation of something that solves {S, A}TSPs for people to laugh at when they're 9000 times faster, but that would hardly constitute a framework for jump-starting...at most it'd outline how we envision adherence to the rules and to the coding guidelines. Look for it in approximately a couple of weeks, give or take, and don't wait for it for reasons other than amusement.

With regards to the latter point, an interval capturing the magnitude of the extreme points could be made public, yes.

[saucam]

Could you please tell me where to register for the contest ?

[cheburashco]

I have a question: are we going to have metric TSP or not?

[Davros]

I solved the Travelling Salesman Problem by refusing to answer the door to them

[WizardsBlade]

As there will be a list of the top scores, would it be ok to enter more then one program? This would allow people to enter earlier and have other competetors see the score to compete against. While not penalizing an early entry if a contestant later sees a better alternative to thier orignal program.

[AlexV]

Originally Posted by saucam

Could you please tell me where to register for the contest ?

Originally Posted by cheburashco

I have a question: are we going to have metric TSP or not?

Originally Posted by WizardsBlade

As there will be a list of the top scores, would it be ok to enter more then one program? This would allow people to enter earlier and have other competetors see the score to compete against. While not penalizing an early entry if a contestant later sees a better alternative to thier orignal program.

saucam: There is no formal registration process, submitting a tentative solution and contact data means you are registered, if the code compiles and does what it should. Please see the rules and regulations provided.

cheburasco: I'm not sure if that is important, the problem spec will be fed into your solver in the form of an adjacency matrix that has per edge costs - whether or not the costs are derived from some particular standard metric or via other means is not that useful as an information, wouldn't you say?

WizardsBlade: There is no limitation on the number of programs one can submit, do so at your own discretion!

[askmahesh]

Hi,

I am wondering if there is a sample i/p file available some place. I could find some files used as i/p from TSPLIB but I can't place the TSPLIB format 2

Mahesh

[cardinaldan]

This might be a stupid question but it lists that the input should be in vector form to hold the adjacency matrix. Am I correct in assuming that we are also to take an integer input specifying the number of nodes represented by the matrix? Also what does major row ordering mean? Thanks.

[AlexV]

Originally Posted by askmahesh

Hi,

I am wondering if there is a sample i/p file available some place. I could find some files used as i/p from TSPLIB but I can't place the TSPLIB format 2

Mahesh

Originally Posted by cardinaldan

This might be a stupid question but it lists that the input should be in vector form to hold the adjacency matrix. Am I correct in assuming that we are also to take an integer input specifying the number of nodes represented by the matrix? Also what does major row ordering mean? Thanks.

askamesh: I am somewhat unsure about the question, but my assumption is that the [2] found after "TSPLIB format" on page 1 of the rules and regulations is what's throwing you off - that is merely a reference number, if you scroll to the end of the doc you will see that [1] is actually a "placeholder" for TSPLIB documentation. In effect, the TSPLIB format is what we'll use to package the problems used for refereeing.

cardinaldan: The number of nodes will be provided, yes (alongside a few other bits of info, a sample will be provided soon to outline the sort of data that you're provided for the solve). Row major ordering means that the vector itself is 1-dimensional, and rows of the matrix are packed in succession...for example, for an M x N matrix, the vector size would be M * N, and the first N elements represent row 1 of the matrix, the next N elements row 2 and so on and so forth. So, if you'd like to retrieve the element found on row i and column j, its address would be (for the above matrix size) i * n + j, with i < M and j < N.

As a general note, I think some clarification is in order as the adjacency matrix terminology may be slightly muddy (the fault for this lies solely at my feet, mind you) : in effect, we'll feed into your solvers a fully specified distance matrix, therefore what you'll get is the costs attached to edges between nodes, rather than just connectivity info, as could've been presumed based on the faulty wording. This will be fixed in a very soon to be uploaded doc. Apologies if this impacted anybody's work in any way.

[cardinaldan]

Another curiousity, does the algorithm need to give a shortest path for a given starting point (e.g. it can take a point as another input)? Or is the goal to find the shortest path while examining all the possible starting points? Thanks.

[Naurava kulkuri]

Hi!

It looks like the links to Rules and Regulations (mandatory) and Coding Guidelines (optional but strongly recommended) are not found (404), so a few questions here.

Is there an upper limit for the problem size? If it's a full weight matrix that's being given, it will be quite heavy on bandwith and GPU memory. The instance size has implications on choosing the most appropriate algorithm (or heuristics to stop within some sensible time).

Which leads to another thing in my mind, related to the already mentioned TSPLIB problem definitions. Would it be possible to include problem instances also in the coordinate form? Like, say, in files berlin52.tsp or ulysses16.tsp?

I know this is already late in the game, but change like this would allow solving bigger instances as the matrices could be calculated on demand on the GPU and only the coordinates need to bet sent over and stored in the (shared) GPU memory. Otherwise, given a large enough weight matrix, it's more worthwhile to calcuate artificial coordinates from the weights and then again transfer them, but I'm not sure if that would be in the spirit of the competition -- different kinds of problem instance transformations.

My first post here. Thanks!

[identity]

After fighting the laziness for a while I finally managed to take a peek at this, however the links in main article (http://www.beyond3d.com/content/articles/121/) seem to be broken, I get 404 when I click the rules & regulations (and also coding guidelines).

Just wanted to check if this is still on

[AlexV]

Quick note: the documentation lack of existence will be fixed a bit later today (many apologies). The questions above will be answered at the same time. Yes, it is very much still on.

[identity]

Originally Posted by AlexV

Quick note: the documentation lack of existence will be fixed a bit later today (many apologies). The questions above will be answered at the same time. Yes, it is very much still on.

Thanks for the reply but I still get 404's on the documents.

[cardinaldan]

I can view the links today but unfortunately too late in the game to ready an entry. Hopefully next contest is a little clearer from the start. Was looking forward to entering.

[AlexV]

cardinaldan: The life of the links has been troubled, apologies for that. As for it being too late I'd not bet on it being the case...As for the other question, shortest path through the graph, without a fixed starting-point.

Naurava: Upper limit is 8192 nodes/cities. Whilst your suggestion about feeding coordinate-form inputs holds definite merit, and we'd love to do that in a future iteration, we'll not do that one for this particular contest, and stick with the boring (and somewhat constraining) full distance matrix approach.

[WizardsBlade]

Well Im almost there, but I am still confused on exactly how you want to input the distance matrix. could you please clarify this or give me an example?

[AlexV]

First of all, it is my pleasure to announce a one month extension for the contest - this should allow everyone involved to play a bit with VS 2012 RTM, and possibly Win 8 RTM. In the same vein, the documentation got updated, and it will hopefully be clearer and more informative now. A sample solution (poor solution at that) will be published this Sunday, to provide further aid. Please grab the updated documentation, and be aware that the email address that acts as a sink for the submissions has changed.

WizardsBlade: any FULL_MATRIX file from the TSPLIB collection is quite representative of how the distance matrix will look.

[WizardsBlade]

Are there some easy (and hard) tsp files with known solution so that we can test how well our programs are wokring? (preferably something small for basic testing and at least one as large as the largest one you plan on testing.)

[AlexV]

Originally Posted by WizardsBlade

Are there some easy (and hard) tsp files with known solution so that we can test how well our programs are wokring? (preferably something small for basic testing and at least one as large as the largest one you plan on testing.)

Indeed there are. Later today there'll also be a suggested testing batches - which is to say TSPs and ATSPs with known optimal tours / optimal tour lengths. Until those are up, I'd suggest using something like PCB442 for moderate size testing and ATT48 or BURMA14 for small scale testing, both of which are available in the TSPLIB collection.

[WizardsBlade]

Could you also include time on the mentioned matriciesto give us at least an idea of how we are doing before anyone turns them in.