Travelling with Style Feedback Thread

Fixed.

 

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.

 

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.

 

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.

 

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.

 

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!

 

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

 

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

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.

 

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

 

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

 

@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

 

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.

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.

Yeah, tell me about it!

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.

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.

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.

 

A new submission is in

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!

 

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

 

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.

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

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

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.

 

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!

 

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.