Travelling with Style Feedback Thread

Discussion in 'GPGPU Technology & Programming' started by AlexV, Jun 17, 2012.

  1. AlexV

    AlexV Heteroscedasticitate
    Moderator Veteran

    Joined:
    Mar 15, 2005
    Messages:
    2,528
    Likes Received:
    107
    All your suggestions, complaints and general contest related messages are welcome here.
     
  2. Ethatron

    Regular Subscriber

    Joined:
    Jan 24, 2010
    Messages:
    856
    Likes Received:
    260
    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. :twisted:

    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. :lol:
     
  3. AlexV

    AlexV Heteroscedasticitate
    Moderator Veteran

    Joined:
    Mar 15, 2005
    Messages:
    2,528
    Likes Received:
    107
    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!:)
     
  4. rapso

    Newcomer

    Joined:
    May 6, 2008
    Messages:
    215
    Likes Received:
    27
    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?
     
  5. AlexV

    AlexV Heteroscedasticitate
    Moderator Veteran

    Joined:
    Mar 15, 2005
    Messages:
    2,528
    Likes Received:
    107
    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.
     
  6. saucam

    Newcomer

    Joined:
    Jun 25, 2012
    Messages:
    1
    Likes Received:
    0
    Could you please tell me where to register for the contest ?
     
  7. cheburashco

    Newcomer

    Joined:
    Jun 27, 2012
    Messages:
    1
    Likes Received:
    0
    I have a question: are we going to have metric TSP or not?
     
  8. Davros

    Legend

    Joined:
    Jun 7, 2004
    Messages:
    14,813
    Likes Received:
    2,229
    I solved the Travelling Salesman Problem by refusing to answer the door to them ;)
     
  9. WizardsBlade

    Newcomer

    Joined:
    Jul 15, 2012
    Messages:
    5
    Likes Received:
    0
    More than one entry?

    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.
     
  10. AlexV

    AlexV Heteroscedasticitate
    Moderator Veteran

    Joined:
    Mar 15, 2005
    Messages:
    2,528
    Likes Received:
    107
    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!:smile:
     
  11. askmahesh

    Newcomer

    Joined:
    Jul 26, 2012
    Messages:
    1
    Likes Received:
    0
    Location:
    Mississauga,ON
    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
     
  12. cardinaldan

    Newcomer

    Joined:
    Jul 29, 2012
    Messages:
    3
    Likes Received:
    0
    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.
     
  13. AlexV

    AlexV Heteroscedasticitate
    Moderator Veteran

    Joined:
    Mar 15, 2005
    Messages:
    2,528
    Likes Received:
    107
    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.
     
  14. cardinaldan

    Newcomer

    Joined:
    Jul 29, 2012
    Messages:
    3
    Likes Received:
    0
    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.
     
  15. Naurava kulkuri

    Newcomer

    Joined:
    Aug 12, 2012
    Messages:
    67
    Likes Received:
    0
    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!
     
  16. identity

    Newcomer

    Joined:
    Aug 15, 2012
    Messages:
    2
    Likes Received:
    0
    links broken in the main article

    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 :)
     
  17. AlexV

    AlexV Heteroscedasticitate
    Moderator Veteran

    Joined:
    Mar 15, 2005
    Messages:
    2,528
    Likes Received:
    107
    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.
     
  18. identity

    Newcomer

    Joined:
    Aug 15, 2012
    Messages:
    2
    Likes Received:
    0
    Thanks for the reply but I still get 404's on the documents.
     
  19. cardinaldan

    Newcomer

    Joined:
    Jul 29, 2012
    Messages:
    3
    Likes Received:
    0
    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.
     
  20. AlexV

    AlexV Heteroscedasticitate
    Moderator Veteran

    Joined:
    Mar 15, 2005
    Messages:
    2,528
    Likes Received:
    107
    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.
     
Loading...

Share This Page

  • About Us

    Beyond3D has been around for over a decade and prides itself on being the best place on the web for in-depth, technically-driven discussion and analysis of 3D graphics hardware. If you love pixels and transistors, you've come to the right place!

    Beyond3D is proudly published by GPU Tools Ltd.
Loading...