[Bernd Paradies]

@Alex: so speaking of knobs. The accuracy of my solver is at around 8%. What should be the accuracy for a solver that is 4x slower to make the switch worth while?
(This is not a trick question, this is a real question I am facing.)

Thanks!

[Naurava kulkuri]

Originally Posted by Bernd Paradies

@Veikko: at least your ATSP is working

If you have a feeling you won't get your ATSP fixed, I think I can lend you a hand with that. At least give some ideas. I suspect you have random restarts there or something, if I guess your approach correctly.

[Naurava kulkuri]

Originally Posted by AlexV

Well, nobody will be shot over run-time, but ask yourself what are the odds of winning with such a long solve. Also, for a source of motivation, peek at how fast Concorde is with code from 2000 something, running on a single core, and using a publically available and currently discontinued LP package (not eve CPlex!).

Or Lin-Kernighan for that matter! And that code isn't that unpenetrable (well, I haven't worked with C or C++ in ages) and for what I understood from taking a quick glimpses, Concorde is probably rather unstable numerically too (if one puts in floating point values).

Now, we can't really hope to beat up Concorde in one fell swoop, but still, we can't allow ourselves to be utterly embarrassed by it, can we?

No we can't! With GPUs and all! Given a bit time, I'd add your ants here, but alas, I put maybe 1-2 hours an evening to this and the function of my skills and code needed has a serious discontinuity.

But in all seriousness, I'd like to win, of course, and running my solver for few minutes will arrive at a rather acceptable solution (clearly less than 1.3 times above optimum), but not as good as Bernd's. Though I haven't run this more than a few minutes.

[AlexV]

Originally Posted by Bernd Paradies

@Alex: so speaking of knobs. The accuracy of my solver is at around 8%. What should be the accuracy for a solver that is 4x slower to make the switch worth while?
(This is not a trick question, this is a real question I am facing.)

Thanks!

Your accuracy seems fine to my eye, in context (well excluding the ATSP case, of course), given that Veikko is pretty much in the same neighbourhood (excluding the larger cases where it would appear that he'll need to give himself some more time). What I'd do (and note that I'm not on the refereeing board or anything, so just take it as 2c), is focus on gaining some more speed in the large instances, whilst holding my accuracy constant(ish). Again, that's just me.

[Naurava kulkuri]

I submitted a new version, with the performance parameters harcoded now. Usage and parameters as before.

This was mostly to get the new version going before further tweaking. I just hope it won't explode.

Now off to sleep...

[Bernd Paradies]

@Alex: thanks for your guidance in regards to faster vs closer.
Have you posted new rankings yet?
I am using this URL:
http://www.beyond3d.com/B3D_AMP_CONT...c_rankings.pdf
Is that the right one?
Also, would you mind putting a time stamp on the page so I know I have the latest?

Thanks!

- Bernd

[Bernd Paradies]

@Veikko: thanks for offering your help! I have a day job, so I can only work in the evenings on ATSP. But I think I am close.

We'll see.

Cheers,

- Bernd

[Naurava kulkuri]

Originally Posted by Bernd Paradies

@Veikko: thanks for offering your help! I have a day job, so I can only work in the evenings on ATSP. But I think I am close.

We'll see.

Sure. If you find a way to put daily jobs and babies on hold for a day or two, please do share your insight with me.

[AlexV]

Page and rankings updated. Rankings are time-stamped, as per Bernd's very good suggestion.

[Bernd Paradies]

@Alex: thanks for updating the rankings!
So, who is leading the TSP category, now?

[Naurava kulkuri]

Hmm, indeed, I wonder the same as Bernd.

I introduced a much more dynamic interruption mechanism to the solver and with current settings on my computer (heh, the works on my computer argument) I get slightly worse tour quality as the previous ad-hocish submission, though clearly faster. Well, that's somewhat a degree of parameter setting.

I wonder what's the problem for my solver on one of the ATSP instances. Let's see if I can deduce something from the size...

[AlexV]

Originally Posted by Bernd Paradies

@Alex: thanks for updating the rankings!
So, who is leading the TSP category, now?

With some back of the envelope calculation, it's marginally Veikko, since he cuts off his processing soon enough at the large instances, and the differential in precision isn't large enough to offset the huge differential in time to solve. Whilst we do favour precision, as already mentioned it will not offset a huge speed difference. Also, the weight a problem holds in the final grade is tied to its size, so larger instances have a bigger impact on the score. That being said, it is quite tight to say the least

[Bernd Paradies]

@Alex: admit it, you can't really tell The costs for getting closer increase as you are getting closer to the optimum! The only way to tell which one is better is by normalizing the results.

@Veikko: Hey, I have a proposal for you.
Shall we normalize our results to, say 360 secs?
In other words I can set the maximum running time at 360 secs. That would allow is to compare apples with oranges.

[Bernd Paradies]

@Alex: I just submitted a new version of my solver with fixes for ATSP.
I also let the solver time out at 360 secs in order to get results we can compare against Veikko's solver.
Also, can I assume that you build Release, x64?

Please let me know if you run into any problems.
I am looking forward to reading the new rankings!

Cheers,

- Bernd

[AlexV]

Originally Posted by Bernd Paradies

@Alex: I just submitted a new version of my solver with fixes for ATSP.
I also let the solver time out at 360 secs in order to get results we can compare against Veikko's solver.
Also, can I assume that you build Release, x64?

Please let me know if you run into any problems.
I am looking forward to reading the new rankings!

Cheers,

- Bernd

Bernd, it would appear that for some reason your new submission isn't showing up, so whenever you get the chance please send again? Compile is Release x32 actually, but let us know if your work is reliant on x64 compilation for optimal performance. Since we placed no requirement on the bitness, we're using the lowest common denominator in this regard.

P.S.: it's not difficult to "know", because each of you gets a numerical value attached based on how you do perf-wise and precision-wise, with the numerical value being computed as a weighted average of the partial scores per-each instance. So personally, I would look at the battle as "hmm, my competitive friend gets this sort of precision in this much time, can I get a similar level in less time"?

Ultimately, your reference should be the other contestant, since it's his submission that you have to beat. How you go about doing that (match time and give better precision, match precision and give better time etc.) is your call.

[Bernd Paradies]

@Alex: I think I accidentally zipped the binaries. The mail came back with a "rejected" note.
Either way, I resent the zip file.

[Naurava kulkuri]

Originally Posted by Bernd Paradies

@Alex: admit it, you can't really tell The costs for getting closer increase as you are getting closer to the optimum! The only way to tell which one is better is by normalizing the results.

I concur, the costs increase even dramatically so.

Which also mean, to some extent that neither of us would actually need 360 seconds especially on smaller instances to get within percentage points of the solutions we see, e.g. in your submission.

You see 360 seconds on my results because of a rather dumb stopping condition, it's much more dynamic now.

@Veikko: Hey, I have a proposal for you.
Shall we normalize our results to, say 360 secs?
In other words I can set the maximum running time at 360 secs. That would allow is to compare apples with oranges.

Apples to oranges indeed. It's all right for me. I don't have an objection (in fact, maybe even higher would be better since I know my solver does make visible progress in any case), but I hope you don't mind waiting for a while?


I still have a few tricks in the sleeve, but it takes at least 13 hours from now for me to get a computer and try crank some code and if I'm lucky/not too tired/etc., I can have something shippable (but it can take another evening too). Currently the tricks are just TODO comments in code, but I think I can pull-off at least one and it should have a (very) beneficial effect very early on in the processing time considering length and especially on the longer tours. Well, at least if we are to believe researchers and I can pull off this particular thing.

[Bernd Paradies]

Hey Veikko, you can go higher than 360. I'll just try to use what you use as a stopper.
13 hours until you get access to a computer?
You must be in the middle of nowhere!

I have a few tricks in my tool chest, too.
Whit is fun!

- Bernd

[AlexV]

Originally Posted by Bernd Paradies

@Alex: I think I accidentally zipped the binaries. The mail came back with a "rejected" note.
Either way, I resent the zip file.

Bernd, I think you may need to spend some more time with the code. For the time being, it fails an assert for non-trivial problem sizes (approximately over 130 nodes or so).

[Naurava kulkuri]

Originally Posted by Bernd Paradies

Hey Veikko, you can go higher than 360. I'll just try to use what you use as a stopper.
13 hours until you get access to a computer?

I have a dynamic stopper now, which checks for change in tour length size in some window, and stops the solver when changes get too small. Though I still have a hard-coded limit too on 360 seconds. Currently especially on the smaller instances it's the "change window check" that stops the solver well before that.

So, you are matching the speed of my solver with quality, which carries more weight in the finald scoring?

You must be in the middle of nowhere!

At work in downtown Tampere, Finland. I'd rather much be implementing ideas to the solver, but can't run away from here now.

I have a few tricks in my tool chest, too.
Whit is fun!

For my part, I just hope I get to the right performance/quality ballpark for what I think I should have after implementing some additions.

[Bernd Paradies]

@Alex: are you seeing those errors for TSP, ATSP, or both?

[AlexV]

They show up in both cases, and are quite size dependent.

[Bernd Paradies]

Hmm, I'll send you another version.
When you say "assert" you mean validation errors?
All asserts melt away in release builds.

- Bernd

[AlexV]

Originally Posted by Bernd Paradies

Hmm, I'll send you another version.
When you say "assert" you mean validation errors?
All asserts melt away in release builds.

- Bernd

Yes, and they leave us staring at a neverending loop of cycles through the graph It took a bit of debugging to find it.

[Naurava kulkuri]

Hello, folks!

It looks like I managed to improve the quality of my tours and lessen the time needed to have them. This comes with a bit of a caution, since it looks like I broke my ATSP calculation in the process. Furthermore, I created a bit of a mess to the code. If I don't need to go to sleep (), I'll try to submit today/tomorrow (it's soon midnight here) so that the results should become visible sooner.