Travelling with Style Feedback Thread

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.

 

@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

 

@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

 

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.

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.

 

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.

 

@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

 

@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

 

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

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.

Quite the opposite...

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

 

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.

 

@Veikko: at least your ATSP is working

 

@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!

 

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.

 

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

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.

 

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