Generalizations of the TSP

Here's my first post in a row of posts detailing what I'm doing in my thesis - and for what it's good. Typically, math students don't necessarily know whether the contents of their thesis can be applied to anything in the real world at all (I'm exaggerating - but for most of them, it's more difficult to find the connection). In my case, however, it's pretty straight forward:

Imagine you're working for UPS and you pick up your truck at 7am in the morning to start your delivery tour. Now, if you're a clever driver, you might want to take a moment and consider how to best approach today's deliveries: what's the shortest (or cheapest or fastest or ...) route to take through town delivering all the packages and, after the last delivery, returning to your depot. That's the Traveling Salesman Problem (TSP) - a very classic example of a problem that's hard to solve to optimality.

Now UPS offers clients to dispatch packages with high or normal priority. High priority packages will be treated with a higher urgency and will typically be delivered before a normal priority package is delivered. In addition to that, a realistic constraint for the delivery of packages is to impose a latest time for delivery, say you have to finish the delivery of all packages by 5pm (receptionists leave rather early, I hear). Trying to come up with a tour for the driver that takes both extensions into consideration (prioritization of deliveries and maximum time allowed for delivery on a single day) is a generalization of the TSP - the Orienteering Problem (OP).

There are a lot more variations of the original TSP. The OP, however, should give you an idea of what such a variation / generalization can look like. In my thesis I'm having a look at these kind of generalizations and trying to come up with algorithms that will solve them to optimality (ie. we find the best tour possible, guaranteed!) but take a lot of computation time or algorithms which only come close to the best tour (which we cannot guarantee, however :-( ) but are fairly quick.

That's enough for a first post - I don't want to scare anybody away before the real fun starts. In the next post I'll try to give a low-math overview of how one can tackle these problems. Let's see whether that's possible!

PS: For the nit-pickers out there: the OP is not really a generalization in the sense that you can solve the TSP by means of an OP. I still like to call it a generalization so bear with me.

IIS and ASP.net

This morning I had to deploy an ASP.net-based application to an IIS. Everything had worked fine on the development system but once I deployed it on our production system, an error message was displayed that didn't give me a clue about what could possibly have gone wrong:

Error initializing the AppDomain

Quickly followed by another error:

The request could not be processed because the application domain could not be created. (translation of Die Anforderung konnte nicht ausgeführt werden, weil die Anwendungsdomäne nicht erstellt werden konnte.)

Google didn't find clear steps to fix the issue but hinted at file permission problems. In fact, I had just extracted a zip file on the server into the application directory instead of creating one manually. Therefore permissions of the containing folder were not reused and just set to some defaults. Comparing and adjusting the file permissions (Security in context menu) of the directory with the permissions of the Inetpub directory fixed the problem.

OpenGL origin

Looks like OpenGL is just doing what all the other 3D frameworks are doing, too. At least this article implies that 3D frameworks generally adopt the maths view of having the origin in the lower left. Good to know!

cocos2d

First time really trying to get something done in iPhone SDK. After struggling ages getting a simple game loop to work - only to discover that I was calling the update routines on the wrong thread - I found a forum post which talked about the cocos2d iPhone 2D game engine.

Have now spent most of the day working on a simple Memory-like game. The engine is pretty straight forward to use once you get to know the APIs. There are a couple of things I didn't quite figure out this time, though - any insights are appreciated:

1. Is there any reason why rendering origin in iPhone / cocos2d / OpenGL seems to be lower left corner instead of upper left? It sure matches the mathematical way of thinking about an origin but AFAIR most of the other frameworks have their origin in the upper left, don't they?
2. To render the game board, I have assembled a Scene using a Layer and a couple of Sprites contained in that Layer where each of the Sprites was supposed to be touchable. I haven't found a way to get that working other than reacting to touches on the Layer and manually checking whether the touch fell within the bounds of one of the Sprites. There must be a better way to do this, right?
3. How does memory management work when you replace Scenes using the Director singleton? You access the Scenes via [Scene node]; so I assume there's autorelease at work.
4. Why do Texture2D.pixelsHigh / .pixelsWide return different values than Texture2D.contentSize?

MacBook Air

Here's another one to start off with: did Apple ever test the first edition MacBook Air in summer time? Don't get me wrong, I love the Air for it's gorgeous design but I just can't stand its' performance!

Even on colder days, the thing becomes so hot it's barely touchable (at least around the ESC-key). But in summer-time, the thing is hot by default! If it was just for the heat, I can live with that. Whenever it's hot, performance goes down big time, however, down to a point where any letter you type is only displayed on screen about a second later!

For something as expensive as the Air I would've expect more. Though, as far as I know, the second edition Air does not have the performance problems anymore (it still gets very hot, though).

iTunes and Single Tracks

So iTunes has this great view on your track collection where you see the cover art for each album you own, one by one.

But every now and then this list is cluttered by album which only contain a single track - it's like having the single, which you love, but not going for the full album. I have loads of those tracks and they mess up my albums view.

Why doesn't iTunes filter those one-track or two-track albums and create a single album entry for those labeled "My Single Compilation" (well, any name will do, I guess) and file all of them into that album entry? The cover art could be a nice patchwork created from each of the individual track's album art.

Hey, Apple, give it a thought!