[Naurava kulkuri]

Originally Posted by Naurava kulkuri

... since it looks like I broke my ATSP calculation in the process...

Fixed.

[Naurava kulkuri]

I need to sleep on before making a submission. It's about twelve hours I'm back again. I apologise for taking this so close to the deadline.

I can say that according to my preliminary testing this is much faster than the previous version whilst maintaining solution quality. Of course with the caveat I haven't submitted my latest code for official scoring.

[Bernd Paradies]

Hi,
I just submitted a new version of my solver. This version comes with optimizations for TSP and support for ASTP. ATSP is pretty lame right now, I am still working on it.

So here is a question for Alex: I get very good results with my ATSP algorithm. But I cannot reconstruct the path. (This is not Floyd-Warshall, where you can reconstruct the path with a little bit of extra work.)

In other words, can I get away with reporting the solution without the path?
I can fill you guys in on the details if necessary.

[Naurava kulkuri]

Originally Posted by Bernd Paradies

In other words, can I get away with reporting the solution without the path? I can fill you guys in on the details if necessary.

May I ask, how do you know if the length you get is correct if you don't have the path? Do you trouble due to some GPU intricacies? This is a serious question. In any event, for my part, if my opinion counts, is that knowing length is better than nothing, but part of the trouble is obtaining the path matching the length.


To other things, my TSP -- and to some degree ATSP -- improvement is algorithmic in nature whereas the previous tweaks were more about refactoring crummy code. I think the changes pack some real impact on my scoring. So that you know what to expect when I asked if you could wait for a while with the time limit setting.

[AlexV]

And rankings updated to account for Bernd's latest submission - good job on the TSP Bernd! Now better work some more on that ATSPTo answer your question, since we set out with the requirement that the tour is written out (I believe you were in favour of this when the public sample showed up missing that capability), the requirement can't be retroactively carved out.

We may consider partial scoring for simply the tour, but that's the referee's call. My strong suggestion is that you don't end up relying on that partial scoring

[Naurava kulkuri]

Heh, rather serious improvements. Now, let's see if I can match those, hopefully this evening.

It may be the question arises again, where to draw the line between quality and speed. Or then I and Bernd engage in "normalization dialogue". But let's see when I get my code submitted.

[Bernd Paradies]

Thanks guys. After normalizing to 360 secs I can finally read the charts!
Veikko, let me know if you want to go higher with the timeout. I'll adjust my timeout then. But I do think normalizing the running times makes it easier to compare our solvers.

I have to say, I am learning a lot about the algorithms that I am using. I use two, let's call them A1 and A2. It turns out that A1 is really good at data sets with n < 3000 and A2 is really good at n >= 3000.
The funny thing is that in the first submission I used both in combination for all data sets. And here is the thing that I learned: the costs for A1 for large data sets don't justify the results. I didn't get the bang for my money. On the other hand A2 is really powerful but takes longer. The performance went up like crazy by just removing A1 from the solver chain for large data sets.

Now on to the final frontier: ATSP! I checked in a pretty lame ATSP solver and it shows in the results. I am working on another one that gives me great results but I cannot reconstruct the paths. Reconstructing those paths in combination with that particular algorithm (A3) has probably never been tried before. And, um, everything has to be done by Sunday.

Cheers!

[Bernd Paradies]

@Veikko: good luck on the last stretch of this competition!
After all this is over we should have a "virtual beer" together!
Alex, you should come too. And where on Earth is Niels?

[Naurava kulkuri]

Originally Posted by Bernd Paradies

Thanks guys. After normalizing to 360 secs I can finally read the charts!
Veikko, let me know if you want to go higher with the timeout. I'll adjust my timeout then. But I do think normalizing the running times makes it easier to compare our solvers.

We'll see if it will be an even enough competition.

And, um, everything has to be done by Sunday.

My ideas aren't revolutionary, rather brute force so far. By reading some research papers I know there are some low-hanging fruits when implemented would make my solver fly like crazy compared to the current version. In any event, we have the time budgets we have. Mine is only some few hours anymore, family matters and all you know, but I think I can still do something maybe on Sunday (tomorrow is a bit difficult).

We'll, I'm back on computer again. I think I have something new tonight and it should offer a match to your hefty performance gains. At least I hope so, but we'll see.

[Naurava kulkuri]

Originally Posted by Bernd Paradies

@Veikko: good luck on the last stretch of this competition!
After all this is over we should have a "virtual beer" together!
Alex, you should come too. And where on Earth is Niels?

Thanks and likewise. How about -virtual- real vodka?

[Bernd Paradies]

Vodka? I have become a lightweight. I'd get drunk after one shot - even virtual vodka!

[Bernd Paradies]

@Veikko: If I don't get my act together on ATSP I would call this a draw.
I have read a few papers too. (I am not smart enough to come up with my own solution.) But I was shocked about the bad quality of the solutions of some of those academic papers. On the surface they all look reasonable and the formulas are intimidating. But when I started implementing some of those I ideas I often realized that the author was hiding very important facts and overstated the impact of their algorithms.

For example, there is this one guy from Japan. He wrote two papers. In the first one he explains a GA algorithm and how to parallelize one part of it. Turns out that on larger data sets the time is spent 99% somewhere else and it doesn't matter at all what his parallel code does.

A year later the same guy wrote a second paper kind of acknowledging that that other part is more important. But instead of solving the problem he presented a method for calculating quickly whether his algorithm should give up or not.

Then another academic guy picked up his paper and stole the indexing scheme (which is indeed clever) without giving the first guy credit for it and "improved" a pre-existing algorithm by using that indexing scheme. But that second guy had a major design flaw in his source code, which he posted - otherwise I wouldn't know. After fixing the bug his claimed improvements melted away.

Ha, ha, ha!

Just be careful about those academic papers!

- Bernd

[Naurava kulkuri]

Originally Posted by Bernd Paradies

@Veikko: If I don't get my act together on ATSP I would call this a draw.

Your solver is rather quick, I have to admit. But on my rig, that is weaker than the test one, I can currently match the results. Though I have some other problems, see further.

I have read a few papers too. (I am not smart enough to come up with my own solution.)

Likewise. Making up my mind on the initial approach was, in hindsight, the most critical decision I could make. I'm glad it paid off. Then there are job, family, GPUs are all new to me, so too metaheuristics for the most part, it was ages ago I wrote C++ and so on. Well, I don't want to make excuses, most people have even more stringent problems, it just happened well I could be on paternity leave during Septemer and could devote enough time to make the initial submission.

But I was shocked about the bad quality of the solutions of some of those academic papers. On the surface they all look reasonable and the formulas are intimidating. But when I started implementing some of those I ideas I often realized that the author was hiding very important facts and overstated the impact of their algorithms.

Yeah, tell me about it!

For example, there is this one guy from Japan. He wrote two papers. In the first one he explains a GA algorithm and how to parallelize one part of it. Turns out that on larger data sets the time is spent 99% somewhere else and it doesn't matter at all what his parallel code does.

My initial search was to find out what is the hotspot I understand well enough to see it is a hotspot and then do something about it.

Then another academic guy picked up his paper and stole the indexing scheme (which is clever) without giving the first guy credit for and "improved" a pre-existing algorithm. But that second guy had a major design flaw in his source code. After fixing it his claimed improvements melted away.

I have seen that happen too. I have scattered around links in my code about papers I have used. I also have tried to credit anyone even for slightest reason. Especially in a competition like this when I need to stand on the shoulders of giants, so to speak, in any case. It's not off from me, I have got the thing I was after the most: experience. We'll you see, in case you want to take a look at my code when it's released. I know there are some people interested to see yours already, it is fast enough to gather interest.

Just be careful about those academic papers!

I believe my main problem is coming up with a stable enough perturbation to escape from local optima. I have a weaker machine than the one used in testing, but I can even get better results on occasion.

The random component also can cause variation in results that is noticeable in the scoring, several percentage points within some timeframe. Oh well.

I'll try to submit my code soon. Our newborn on one hand causes nightly trouble, on the other hand I have a reason to be awake.

[Naurava kulkuri]

Hi!

The new code is in. I'm off to sleep now, but I'll peek in "tomorrow" (that'd be today) and let you know if start working on further things.

Cheers!

[AlexV]

Results updated. Not too shabby Veikko, if I do say so myself. Though I must admit that I am left wondering why nobody likes the ATSP much

Bernd: Niels won't be joining your travels on this occasion (but there will be other contests in the future where you may cross swords...err...codes).

[Bernd Paradies]

@Veikko: very impressive, indeed.
Jeez, am I still leading for TSP - but the distance shrank?
In other words you are in the process of catching up?
Or am I already on 2nd place for TSP?

Alex?

[Naurava kulkuri]

Originally Posted by Bernd Paradies

@Veikko: very impressive, indeed.

Thank you, thank you. I think I just made into my code one of the approaches you are doing already. There are some crummy spots to shave off, but as noted, I'll need to see when to do the cleaning.

Jeez, am I still leading for TSP - but the distance shrank?

It would appear so, if quality is the stronger measure.

In other words you are in the process of catching up?

On my weaker machine those results are on the lower side. Oh well, the random components, maybe I should just resubmit and see how it changes... The [7300, 7500] category was on the better side of runs, judging from my computer.

Or then I could use another algorithm, which would yield better results in approximately the same amount of time. One kind of problem is that there's plenty (well, enough) of such code in the Internjet, but I think I need to implement these on my own so I can say in good conscience it's enough an effort of my own. Basic approach problems...

Or am I already on 2nd place for TSP? Alex?

Do tell me. I think I'll do at least some intermediary tweaks, if not some new stuff (most probably on Sunday if I do), which should give a better edge. One option would be to just process longer, which should yield several percentange ponts better results in mere seconds.

Hmm, I tried also /favor:AMD64, but my pre-release version of Visual Studio said it doesn't recognise the switch. Does anyone know if it should work? Maybe I should turn on at least the AVX switch and also do x64 version. Especially the ATSP case should benefit of it.

[Naurava kulkuri]

Originally Posted by AlexV

Though I must admit that I am left wondering why nobody likes the ATSP much

One has to search through n! routes instead of n!/2. The "landscape" is much more rugged, and in addition, one has to keep track on direction too! If Bernd gets his ATSP solver into better shape with those subsecond times, I'd still wonder how close to optimum he would get in, say, 120 seconds.

I have multiple ideas I'm rather certain would be fruitful in the context of this competition. Too little time, I should have started working on them a few weeks ago.

A fast asymmetric solver would be of a lot commercial interest too!

[Ethatron]

Originally Posted by Bernd Paradies

@Veikko: good luck on the last stretch of this competition!
After all this is over we should have a "virtual beer" together!
Alex, you should come too. And where on Earth is Niels?

I'm in El Salvador.
Just a note for the curious: I didn't really want to implement an approximating algorithm, neither did I want to reimplement Concorde, so I was just banging on good old Held-Karp. It'll give you the exact route, but not fast enough. Code is going to be available, don't want spoil it till Sunday.
It's maybe visible I know more about optimization on a CPU & GPUs than about an acceptable TSP-solver. :P

[AlexV]

Veikko, Bernd: I would focus on generating the best possible submission without concern for the positioning versus the competitor...after all, it is quite opaque what he is or isn't doing. At this point you're reasonably balanced, so with one strong pull it can go either way. Tomorrow morning, on the eve of the end-of-times you'll get to see more clearly how you sit one versus the other.

Also, if you gentlemen feel that x64 builds are a better case for you by all means, add an x64 compile target/configuration and we'll explore that too. Note that we'll still go with the lowest common denominator, so if only one of you has an x64 build we'll score based on x32.

[Bernd Paradies]

Hello Alex,

I just submitted my 4th Solver version for Beyond3D's C++ AMP Contest!

I also hard-coded the timeout limits accordingly so they would match with Veikko's running times from the latest rankings chart. Now, if he submits another version those running times may change.
For that reason I have added support for setting the timeout value in ms via command line option.
Just add "-timeout ms" to the command line before the tsp file name.

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

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

Cheers,

- Bernd

[Bernd Paradies]

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

Or GMT?

This might get important...

[Bernd Paradies]

Hey Niels, have fun in El Salvador!

- Bernd

[Bernd Paradies]

@Alex: x32 is fine with me!

[Naurava kulkuri]

Hi!

I made the timeout window parameters slightly larger, so it should calculate more. No idea how it effects the results on test machine, though.