[Bernd Paradies]

Thanks, Naurava. Yes, I have also been elected as one of the finalists. Who's the third?
Come on out and join the party!

In regards to tweaking the algorithms in the final round I came to the same conclusion as you did in one of your posts in this forum: assuming that your algorithm doesn't have any bugs or inefficiencies at one point you can either be closer to the optimal solution, or faster.

This all comes down to the penalty function that is applied to the results.
For example, what algorithm would win if the optimal solution were, say, 1000?
Algorithm A: arrives at 800 in 5 minutes,
Algorithm B: arrives at 1000 in 3 hours.

This is really up to the organizer of this contest to decide. What is the penalty for being 200 points off for Algorithm A in this case?

I am glad I don't have to make that call!

Also, unless the organizers disclosed the penalty function and size of the problem set (number of cities) I don't see how I should tweak my algorithms. Somebody needs to tell me what's more important: closer or faster?

You can't have both. After all TSP is np-complete.

Cheers,

- Bernd

[AlexV]

Originally Posted by Bernd Paradies

closer or faster?

Closer beats faster, within our grading scheme, and within reason (so an exact solve that takes an age will not win against a +-5% one that if fast, whereas an instantaneous solve that is 50% off will not win either). Largest problem instance is 7500 nodes for the TSP (slight reduction versus the former 8192 quoted limit). The example that Bernd quoted is extreme, and would indeed pose a problem, but in the grading scheme that is employed the faster solution would win. If it were much further off though, it would be treated as invalid.

Apologies for the result publishing delay (this will of course adjust your time for final submission accordingly), just a few wrinkles to sort out.

[Naurava kulkuri]

Originally Posted by AlexV

Closer beats faster, within our grading scheme, and within reason (so an exact solve that takes an age will not win against a +-5% one that if fast, whereas an instantaneous solve that is 50% off will not win either).

Sounds reasonable. But no more of that so as not to divulge too much information on my approach at this point.

Largest problem instance is 7500 nodes for the TSP (slight reduction versus the former 8192 quoted limit).

Meh, I for one would welcome even instances going well over 10 000 or so long as there's memory to store floating point coordinates to the GPU memory. But let's see if I can tweak the GPU codes with this information as I had some problems with data fitting...

Apologies for the result publishing delay (this will of course adjust your time for final submission accordingly), just a few wrinkles to sort out.

No problems. Initially I entered to just learn GPU programming and do something that feels more relaxing than daily drudgery at work.

Maybe I continue after this to add a Bing/Nokia map and some other thingies to the mix. If I only had time, this would be worth blogging too!

[Naurava kulkuri]

Hi!

A thought occurred.

would it be considered cheating if one changed the floating point matrix to integers? I'm considering a situation where the decimal fractions of all elements are zeroes, as in the TSPLib EUC_2D instances.

If that's all right, can knowledge of the problem type be used when reading data and constructing the matrix or should the solver take the initial row-major square floating point matrix and transform that to preserve the interface given in contest rules (first checking every entry)?

And in general, if the problem type can be used, one doesn't even need a row major matrix in all instances, like the aforementioned EUC_2D (though one could do transformations with some price to be paid in time).

[Bernd Paradies]

As far as I know all TSPLib data files use rounded numbers. But this contest asks for using a distance matrix as input data. And the values in the distance matrix are definitely floats. Are you suggesting using distance matrices with ints?

Best,

- Bernd

[Naurava kulkuri]

Originally Posted by Bernd Paradies

As far as I know all TSPLib data files use rounded numbers. But this contest asks for using a distance matrix as input data. And the values in the distance matrix are definitely floats. Are you suggesting using distance matrices with ints?

Basically that is what I suggest.

I was wondering if it were within the rules to check if the fraction part of all of the floating point values would be zero and if so, let the solver use integers instead of floating point values. All this would be included in timing, of course. A related idea, a step further I would say, would be to transform symmetric distance matrices to integer coordinates.

This is just evaluating options. I'm not sure going that route would the smartest option, for me at least, since there are other possibilities to speed up my code.

[AlexV]

Fundamentally, what your solved does with the distance matrix once it eats it is your responsibility only - if you want to do the conversion from that starting point, it is allowed. However you cannot assume anything about what happens upstream (in spite of the apparent transparence). So, summing up, if you want to invest some of the solve time towards performing the change from float to int, you are allowed to do so, but everything that sits on above the distance matrix that gets served is to be regarded as opaque.

[Naurava kulkuri]

Hoh!

It looks like that in addition to the mess I wrote about here earlier, I manged to put a handbrake on too! Then I also noticed my buffer usage looks rather non-smart too, in hindsight, and looks like a promising source for performance tweaks.

Now, I wonder, should I introduce them as separate fixes or all at the same time? In the same amount of time I get better routes, as the code manages to calculate vastly more routes.

[AlexV]

Gentlemen, the page has been updated with the intermediate ranking. The contest dedicated email awaits your inquiries, and updated submissions. Once again apologies for the delay.

[Naurava kulkuri]

Originally Posted by AlexV

Gentlemen, the page has been updated with the intermediate ranking. The contest dedicated email awaits your inquiries, and updated submissions. Once again apologies for the delay.

No problems.

A few questions:

• I probably can suppose Bernd has the lead currently?
• Are the correctness rankings determined by problem instances of at most 500 nodes in size?
• Are the performance rankings of ATSP instances determined by problem instances of at most 500 nodes in size?
• Since I have some knobs there, does it matter how they behave or does someone just adjust them to "sufficiently long run" and check for the intermediary results for performance and correctness?

And yeah, I have significantly faster version coming. It remains to be seen if it's fast enough.

[AlexV]

Originally Posted by Naurava kulkuri

No problems.


A few questions:

• I probably can suppose Bernd has the lead currently?
• Are the correctness rankings determined by problem instances of at most 500 nodes in size?
• Are the performance rankings of ATSP instances determined by problem instances of at most 500 nodes in size?
• Since I have some knobs there, does it matter how they behave or does someone just adjust them to "sufficiently long run" and check for the intermediary results for performance and correctness?

And yeah, I have significantly faster version coming. It remains to be seen if it's fast enough.

Hello Naurava,

• Bernd's solver doesn't currently solve any of the ATSP instances within an acceptable correctness tolerance (everything that's more than 30% off is tagged as invalid, hence the double strikethrough);
• Eh no, that is an error in the graph that I will correct (pun accidental but probably convenient) now; the charts are symmetric so the performance measurements and correctness measurements are taken with the same sample;
• That is correct bar one exception (one larger instance may or may not be included);
• Your default knobs were used - it is the contestant's responsibility to setup the solver to do its best, after all

Good luck with the faster version! A few notes about the tests: they were taken on a machine with 16 GB of RAM, an FX-8150 processor, Radeon 7970 Video card with a Tahiti GPU (normal edition, not GHz), Windows 8 final with all updates and Visual Studio 2012 with Quarterly update 1 CTP 3 installed.

[AlexV]

Also, please note that you have up until the coming Sunday for implementing tweaks and refinements - we have pushed the term forward given that there was a delay in bringing about the rankings.

In tandem with this, I'll unveil the identity of the third contestant, whilst mentioning that there are some problems with the submission that for the time being prevent us from including it in the grading process. The gentleman's name is Niels Fröhling (Etathron on these forums), and if he ships us an updated submission that takes care of the issue he'll be competing with you for the gold as well.

[Ethatron]

LOL, haven't been called a gentleman before (though my nickname in the beginning of the 90's was gENtLe [uhm, apparent where I learned assembler?])

I think though, having helped AMD fix/find a bug in their shader-compiler will stay my only contribution. I learned a lot of course, besides.

[Bernd Paradies]

@Alex: thanks for posting the rankings! I find the charts a bit hard to read. I understand that my ATSP results are disqualified. But it is unclear to me who is leading in the TSP category.
Veikko, because my ATSP results are disqualified?

For example, who is better at 500/600 TSP?:
My solution is faster (1.988 vs 40) but Veikko's solution is closer (5.21% vs 6.42%)
Can I assume that I lead the TSP category?

Thanks,

- Bernd

[Bernd Paradies]

@Veikko: I didn't know your real name. Sorry for addressing you as Nauvara. Are you from Finland?

Good luck, may the penalty functions be ever in your favor!

- Bernd

[Naurava kulkuri]

Originally Posted by Bernd Paradies

@Veikko: I didn't know your real name. Sorry for addressing you as Nauvara. Are you from Finland?

No need to apologize, that's my nick here (I just assume you and Niels are German speaking, though the joke probably requires knowing Finnish ). Yep, I'm from Finland.

Good luck, may the penalty functions be ever in your favor!

Likewise! And be warned, I have have twice as fast TSP solver now, which also factors markedly to route quality (and I need to check my defaults since the results were rather poor even to my crippled version).

Let's hope you come up something with your ATSP part too.

[Naurava kulkuri]

Originally Posted by AlexV

... they were taken on a machine with 16 GB of RAM, an FX-8150 processor, Radeon 7970 Video card with a Tahiti GPU...

Hmm, does that mean I can turn on AVX optimizations and the binary won't crash on test machines because of missing instructions?

I don't have a machine with AVX intruction set to test performance, but I came curious.

[AlexV]

Originally Posted by Bernd Paradies

@Alex: thanks for posting the rankings! I find the charts a bit hard to read. I understand that my ATSP results are disqualified. But it is unclear to me who is leading in the TSP category.
Veikko, because my ATSP results are disqualified?

For example, who is better at 500/600 TSP?:
My solution is faster (1.988 vs 40) but Veikko's solution is closer (5.21% vs 6.42%)
Can I assume that I lead the TSP category?

Thanks,

- Bernd

Bernd: It would appear that my chart making skills have grown rusty - sorry for that one Your assumption about leadership in the TSP category is correct, as is the one about the state of things in the ATSP case.

Veikko: Your code has been verified to compile with AVX turned on just fine, so yes if you want to turn that on by default you definitely can. On the topic of your defaults (and this applies to both contestants), my humble suggestion is that you set them up yourself to the best of your ability so that for the measurements one needs but compile and run (in the extreme), with perhaps only one or two lines added to hook into the test harness. Nobody knows your code better than you do, so you're the ones that can make sure that it does its best!

[Bernd Paradies]

@Alex: I think, my chart *reading* skills are more rusty than your chart *marking* skills!
So if I sent you an updated version today, will you then update the charts as soon as possible?
Will Veikko and I get (more or less) immediate feedback on our tweaks?

- Bernd

[Bernd Paradies]

@Veikko: yeah, my ATSP code used to work but then broke. I'll fix it.
And, yes: I am a German. But I live in the US now.

Your solver is now twice as fast? That's impressive! But are you also closer?
The charts look really funny to me: My accuracy is stable at around 8% but my running time declines while your running time is stable at around 40secs but your accuracy declines as the problem set grows.

That tells me that you are probably using some sort of a Generational Algorithm (GA) where you i.e. let some ants crawl around. I tried one of those too. But the problem was, though, that I didn't know when to stop. I found myself forced to set arbitrary stops - like I suspect you did in your case with 40 seconds.

There is a different class of algorithms (not necessarily better, just different), that work more like optimizers. Those algorithms optimize as best as they can and naturally stop when they can't find anything to optimize anymore.

I am using two of those. That's why the comparison chart looks so funny in my opinion.

Cheers,

- Bernd

[Naurava kulkuri]

Originally Posted by Bernd Paradies

@Veikko: yeah, my ATSP code used to work but then broke. I'll fix it.
And, yes: I am a German. But I live in the US now.

Your solver is now twice as fast? That's impressive! But are you also closer?

Easily closer (even within that 40 seconds seen in the charts).

The charts look really funny to me: My accuracy is stable at around 8% but my running time declines while your running time is stable at around 40secs but your accuracy declines as the problem set grows.

In my case that's only because the solver has a time limit and it looks like it was set to 40 seconds. Longer routes required more crunching, but especially that part should be alleviated now.

That tells me that you are probably using some sort of a Generational Algorithm (GA) where you i.e. let some ants crawl around. I tried one of those too.

Quite the opposite...

There is a different class of algorithms (not necessarily better, just different), that work more like optimizers. Those algorithms optimize as best as they can and naturally stop when they can't find anything to optimize anymore.

... I think we are on the same page here, though now I have a faster version coming. Let's see if I get it done today.

The problem still is about stopping, though. But if time isn't that much of an issue here, I can set a higher stopping time or disable it altogether.

[AlexV]

Results are updated as versions get sent in (bar the lag needed for the testing, of course). Feedback is also as rapid as possible. Nice to see you gentlemen exchanging ideas

[Naurava kulkuri]

Originally Posted by AlexV

Nice to see you gentlemen exchanging ideas

Or just teasing out details. If Bernd's (general) approach indeed is the same as mine, I'd be interested to know how fast his ATSP code will be as that's my weak point -- or I thought it was.

Well, it all will be public when this competition is over and everyone will see there are huge improvement possibilities on my GPU code, and other accelerating stuff can be easily added. I think I just concentrate on fixing the most glaring flaws now and seeing what I can do stop the solver appropriately. Question: How many seconds is too much? I see 1500 seconds looks like being allrightish still.

Hmm, I think I need to modify my "knobs" a bit, most likely disable them. They are good to exist if one knows it's a, say, clustered instance coming and behave accordingly, but alas, that's not the case here.

[AlexV]

Originally Posted by Naurava kulkuri

I think I just concentrate on fixing the most glaring flaws now and seeing what I can do stop the solver appropriately. Question: How many seconds is too much? I see 1500 seconds looks like being allrightish still.

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

[Bernd Paradies]

@Veikko: at least your ATSP is working