[Naurava kulkuri]

Originally Posted by Bernd Paradies

Just add "-timeout ms" to the command line before the tsp file name.

I too have such a switch.

I am willing to accept any comparison based on the timeout that Veikko chooses!

This is nearing a bit of a draw in the sense both of us can "target" the other one. Unless something happens, of course, say, with your latest submission.

Hey Veikko, you are a tough sparring partner. Not sure whether I can keep up with you.
I am running out of steam...

Likewise. My hat goes off to you!

Originally Posted by Bernd Paradies

@Alex: when is exactly the deadline?
Sun, 10/28/2012, 11:59 PM PST?

Or GMT?

This might get important...

Perhaps so. I'd love to tweak some parameters and "clean places", but I'm so out of time and days for "wee hours". A bit annoying to know I have a few so clear places to boost performance noticeably.

[AlexV]

Updated ranking should be soon ASAP (read in at most an hour or so). Noted about your switchy switches. In terms of the deadline being 23:59 GMT on Sunday, nobody will be shot if he submits later than that within a reasonable timeframe, which means before 08:00 GMT on Monday

[Bernd Paradies]

Hmm, where are the rankings?

[Bernd Paradies]

Oops, I forgot to refresh the browser and I didn't see Alex's post.
I didn't mean to be pushy!

[Bernd Paradies]

I see, the new rankings are out!
Do you guys agree that I am still leading the TSP category?
What happened to ATSP?
Did my solver fail for 400-500?
Were the tours incorrect?

[AlexV]

Rankings updated. Note that we haven't used the timeout switches (yet), but will do so for the final scoring / tomorrow's rankings, if you still want that. We also took the liberty of enabling AVX, Full Optimization, Favour Speed and Parallel Code Generation (albeit neither of the competing solvers was much liked by the VS2012 machinery, so no automatic Vec or Par to be had). If you disagree with either of those choices, let us know.

Bernd: your new ATSP solver is pretty cool as far as we can tell until it breaks down (probably due to the causes you outlined in the text for the submission) - where there are no values the solver crashed. Fixing that would be rather beneficial, I would say

Good luck to you both with the final grind!

[Bernd Paradies]

ok, I'll work on it.
But what really surprised me is the 23% for ATSP 100,200 nodes.
This doesn't make sense to me:
TSP 200,300 yields 5.51% in 3secs
But ATSP 100,200 yields 23% in 15ms.
This is really suspicious. Are you sure those numbers are correct?

Is there any chance to get the data sets (if Veikko agrees) so I can debug the mess?
My ATSP data sets work.

- Bernd

[Bernd Paradies]

I submitted another version.

This is kind of a shot in the dark in order to fix ATSP.
I also adjusted my timeout values to Veikko's except for the 7300,7500 TSP data sets.
I think 7% for 180 secs is better than 14% for 102 secs.

Cheers,

- Bernd

[AlexV]

Originally Posted by Bernd Paradies

Is there any chance to get the data sets (if Veikko agrees) so I can debug the mess?

Probably not, however I can direct you to two instances in TSPLIB that exhibit the same crashy behaviour: kro124p and rbg323. The results are repeatable on the test machine, but if you feel they're incorrect it's possible we're not getting the execution parameters right so drop us a line with exactly how a call to the solver should look.

[Bernd Paradies]

Ah, thanks so much. Now I have something to work on!

- Bernd

[AlexV]

Rankings updated with Bernd's latest submission. I hope nobody is against the smell of competition in the morning!

[Bernd Paradies]

Oh man, this is tight. I would say I still lead TSP because of better results for the 5000 and above sets.
ATSP is a total disaster.

- Bernd

[Naurava kulkuri]

Oh no, this is going to get difficult. So close and so on. I'll see if I can do something... Pass midnight wasn't a problem then? Oh, so difficult now make a decision on normalizing on these time settings if I'm in the losing end, but on the other hand, the results are within error marginals as far as I can judge from the results I have on my computer.

Such is life.

[Naurava kulkuri]

Originally Posted by AlexV

Rankings updated with Bernd's latest submission. I hope nobody is against the smell of competition in the morning!

Couldn't accomondate daily routines for this, but I'll give a shot if I can make up something quick (during the evening/midnight).

[AlexV]

Rankings updated with Veikko's latest submission.

[Bernd Paradies]

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

[Bernd Paradies]

Just saw the new rankings.
I think my ATSP got better!

- Bernd

[Bernd Paradies]

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

[Naurava kulkuri]

Originally Posted by Bernd Paradies

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!

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.

[AlexV]

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

[Naurava kulkuri]

Originally Posted by AlexV

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

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).

[Bernd Paradies]

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

[Naurava kulkuri]

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

[Naurava kulkuri]

Originally Posted by Bernd Paradies

What a finish! So ATSP is broken for both of us?

I wonder how did I broke my ATSP!

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.

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).

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.

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).

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.

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.

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

As one couldn't but comply.

Well, off to Windows 8 land now...

[AlexV]

Originally Posted by Bernd Paradies

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

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".