Travelling with Style Feedback Thread

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

  1. Bernd Paradies

    Newcomer

    Joined:
    Sep 3, 2012
    Messages:
    54
    Likes Received:
    0
    Hi Alex,

    this might be my last submission.I didn't change the timeout values and the TSP solvers.

    But I made ATSP super robust.The ATSP solver tries to reconstruct the ATSP tour and it now knows when things are going downhill. Instead of crashing the solver (it's actually a utility function) now returns with an error.

    I print out a big error message about the broken tour - but the result should be accurate.
    I'll try to improve the algorithm further. kro124p succeeds but rbg443 yields incorrect tours.

    Veikko, you kicked my ass at ATSP!

    Cheers,

    - Bernd
     
  2. Bernd Paradies

    Newcomer

    Joined:
    Sep 3, 2012
    Messages:
    54
    Likes Received:
    0
    Just saw the new rankings.
    I think my ATSP got better!

    - Bernd
     
  3. Bernd Paradies

    Newcomer

    Joined:
    Sep 3, 2012
    Messages:
    54
    Likes Received:
    0
    That's it, guys. I am done.
    Just submitted my last version.

    I found a situation where the code could run into an infinite loop and fixed it. I adjusted the timeout for 7000 and up category from 200 to 150. Then I had an idea how to improve the reconstruction but that didn't work out.

    Thanks so much for everything.
    See you tomorrow here at this board!

    Cheers,

    - Bernd
     
  4. Naurava kulkuri

    Newcomer

    Joined:
    Aug 12, 2012
    Messages:
    67
    Likes Received:
    0
    I see you got better at ATSP! See you today here. I also "submitted" new code last night, but I forgot to attach the zip file. :( Let's see if I get shot now submitting it later again. It's perturbation should be more stable now and the yielded paths should also be shorter. We'll see how things progress.
     
    #144 Naurava kulkuri, Oct 29, 2012
    Last edited by a moderator: Oct 29, 2012
  5. AlexV

    AlexV Heteroscedasticitate
    Moderator Veteran

    Joined:
    Mar 15, 2005
    Messages:
    2,528
    Likes Received:
    107
    Thank you gentlemen for your epic struggle! I've updated the rankings one last time, based on your final submissions...which seem to have completely broken ATSPs for everyone. In this context, there are two questions addressed to you:

    1. would you like us to use your last submission, or another one in the chain of submissions? Choose only one please, not a mishmash:smile:
    2. do you want to be time matched and be separated by corectness? Bernd suggested this, and we are ambivalent in this regard.

    Note that if you don't take advantage of any of the two facilities outlined above, we'll take the latest submission and its parameters as the best ones you want us to account for. Based strictly on the current state of affairs, Veikko marginally wins, before the judge assessment of the code is factored in.
     
  6. Naurava kulkuri

    Newcomer

    Joined:
    Aug 12, 2012
    Messages:
    67
    Likes Received:
    0
    Cheesh! What a situation. Let me read this a better. This is just a short note to tell I'm here now. I fell asleep whilst putting our children to sleep (sorry for the delay).
     
  7. Bernd Paradies

    Newcomer

    Joined:
    Sep 3, 2012
    Messages:
    54
    Likes Received:
    0
    What a finish! So ATSP is broken for both of us?

    To answer #1:
    If that's the case then please use the last build that worked, which should be my 6th submission (amp-floyd-2opt-2012-10-28b.zip).

    To answer #2:
    As mentioned before I would be willing to go with time matched and separated by correctness - if the correctness is not compromised too much. An extreme example would be using 5 secs for TSP's 7300,7500. If you did that you would pretty much get random results. For the data sets that I am seeing I only have a tiny problem with 7300,7500 for TSP. Veikko uses 40 secs for 7300,7500 and arrives at 14% while I use 150 secs for 6%. Perhaps we should settle for something in the middle.

    I have one additional suggestion: run all tests 3 times and take the best results.
    My solver randomizes initial tours, so each run is slightly different. That shouldn't matter for high timeout values (i.e. 1h for TSP 7300,7500). But all of the timeout values seem small. If the timeout values are too small things get dicey.

    Perhaps you should set the timeouts for each categories and Veikko and I have to comply.
    That would probably the fairest outcome.

    Cheers,

    - Bernd
     
  8. Naurava kulkuri

    Newcomer

    Joined:
    Aug 12, 2012
    Messages:
    67
    Likes Received:
    0
    A bit peculiar that ATSP thing. Is it certain they are broken or did just something happen on the test rig? I took a peek at the code and some test output files I have and the results should indicate more calculation in every instance.

    In the TSP case the results could be around the correct ballpark regarding my latest submission concerning perturbation changes, but I would have assumed the calculation would have a longer "tail" and actually calculate for well over 100 seconds and actually have better quality results.

    Does all this chatter matter? I'd need to switch to a dual-booted pre-release Windows 8 to check (it would take a few minutes) to actually compile something as my trial VS 2012 license expired some time ago on my Windows 7 (which I'm on currently).

    Winning is all good and well, but I wouldn't like to rob Bernd for the hard work he did, so I'd be inclined to go towards choosing some previous submission. But I'll boot to Windows 8, just a sec...
     
  9. Naurava kulkuri

    Newcomer

    Joined:
    Aug 12, 2012
    Messages:
    67
    Likes Received:
    0
    I wonder how did I broke my ATSP!

    I'd be in about 120% in around 0.2-0.3 seconds. My trouble starts there, so to speak, progressing slowly but rather surely to a better outcome, depending on how randomness is kicking in (it's not taking tours at random, but modifying them at random).

    Perhaps. I'm not sure if being fast or being really slow is good for me in this regard. Or as with the new perturbation I put in, I could actually have comparable results in comparable time (on my machine, it depends from the run, enough variation this to be little suspectible).

    To some degree. I use currently exponential moving average to shut down the solver if it doesn't make progress fast enough. As it stands, depending on randomness, it may cause the solver to go off too soon, or too late, to win either by speed or quality. :p

    As one couldn't but comply. :)

    Well, off to Windows 8 land now...
     
  10. AlexV

    AlexV Heteroscedasticitate
    Moderator Veteran

    Joined:
    Mar 15, 2005
    Messages:
    2,528
    Likes Received:
    107
    Actually I was suggesting normalizing versus the fastest submission, which is to say whichever of you is faster in a particular test and then set that particular time as the upper bound. Measurements are takes as best out of 5 runs actually.

    Veikko: your prior submissions behave fine...as in in line with what they were doing before, so the rig is in the same state. Also, you may have misunderstood me, you cannot submit new code, you can just choose one of the already submitted variants as your "champion".
     
  11. Naurava kulkuri

    Newcomer

    Joined:
    Aug 12, 2012
    Messages:
    67
    Likes Received:
    0
    Hmm, I may have worded badly. I was thinking along the lines that with that many seconds of calculation, I would assume one part of my algorithm is active, which shouldn't miss that badly the 130% part. I changed the output texts somewhat, so if the test rig is reading those directly, that may cause trouble.

    Indeed about the champion, I wonder if it were the previous one then, which had "working ATSP", but a bit worse perturbation. First I understood we have to choose it in tandem with Bernd, but I just realised we've been submitting code "out of sync".
     
  12. AlexV

    AlexV Heteroscedasticitate
    Moderator Veteran

    Joined:
    Mar 15, 2005
    Messages:
    2,528
    Likes Received:
    107
    Each chooses what submission he wants to position as best, and we use those numbers. Are you saying your output is incorrect for the last submission?
     
  13. Naurava kulkuri

    Newcomer

    Joined:
    Aug 12, 2012
    Messages:
    67
    Likes Received:
    0
    No, but it contains more lines for statistical information before outputting path information.

    (BRB, I need check something outside...)
     
  14. AlexV

    AlexV Heteroscedasticitate
    Moderator Veteran

    Joined:
    Mar 15, 2005
    Messages:
    2,528
    Likes Received:
    107
    That should have no impact given what we're reading from it...also, for smaller problems the result are accurate and good (somewhat similar with Bernd's latest, actually). Larger ATSPs are evil is a possible explanation...very scientific too!
     
  15. Naurava kulkuri

    Newcomer

    Joined:
    Aug 12, 2012
    Messages:
    67
    Likes Received:
    0
    Aah, has the test set changed/more reveleaded? It's just that I'm a bit puzzled that obviously I shouldn't go with a "broken ATSP implementation", which is in this release (which should be more or less the same as previously as it has two parts), but I believe the latest submission should also sport an improved pertubation function and thus fare better at least in the larger TSP cases (unless I broke it in the smaller ones :p).

    <edit: In the pdf, the largest ATSP instance I see are still marked as "[450, 500] nodes".
     
    #155 Naurava kulkuri, Oct 29, 2012
    Last edited by a moderator: Oct 29, 2012
  16. Naurava kulkuri

    Newcomer

    Joined:
    Aug 12, 2012
    Messages:
    67
    Likes Received:
    0
    I really need to go to sleep already (past midnight here, I'll be on-line in about 9 hours, I believe), but if a decision regarding my solver should be done, it should be the latest one (submission 6) if I'm to assume the ATSP isn't broken on instances smaller than, say rbg403.atsp and rbg443.atsp (judging that TSPLib instances were part of the set when Bernd debugged his solver) or that is, if the solver isn't broken for node sizes below 500.
     
  17. AlexV

    AlexV Heteroscedasticitate
    Moderator Veteran

    Joined:
    Mar 15, 2005
    Messages:
    2,528
    Likes Received:
    107
    That is correct... you do well at 53 nodes:razz:
     
  18. Naurava kulkuri

    Newcomer

    Joined:
    Aug 12, 2012
    Messages:
    67
    Likes Received:
    0
    Hmm, rather strange. I took the code I submitted, compiled on my work machine and the output looks all right (I can send the log if needed).

    In any event, can I just write here you take what you consider to be my best submission and run it the way you and/or Bernd like to run? I'd hate to keep you waiting between this time zoney thing. Especially since I'm not sure which one is my best submission. If I'm forced to tell something, I remember submission 5 didn't have ATSP problems and its TSP performance was acceptable. :)

    <edit: And to add, I meant before rbg403.atsp and rbg443.atsp were included in the set "still functioning" (to clarify).
     
    #158 Naurava kulkuri, Oct 30, 2012
    Last edited by a moderator: Oct 30, 2012
  19. Naurava kulkuri

    Newcomer

    Joined:
    Aug 12, 2012
    Messages:
    67
    Likes Received:
    0
    To add here, Bernd, if you want to ask about the code or approach (when it comes available), go ahead. I answer to the best of my ability either here or elsewhere.

    Funny you happened to mention utility functions, as I've been viewing stuff like
    http://www.ceet.niu.edu/faculty/ghrayeb/IENG576s04/papers/Local%20Search/local%20search%20for%20tsp.pdf
    http://www.cleveralgorithms.com/nature-inspired/stochastic/guided_local_search.html

    ants and alike to supplement my code. But as said, my approach is currently really rather brute-forcing, albeit quite quickly.
     
  20. Bernd Paradies

    Newcomer

    Joined:
    Sep 3, 2012
    Messages:
    54
    Likes Received:
    0
    Thanks, Veikko!
    We should exchange notes after all this is done.
    I'll be travelling the next few days (as you did last week). Don't know when I will be able to check my emails, though. In the worst case you guys won't hear from me until Sun 11/4.
     
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...