All tied up

Velcro users of the world, now you will have to go back to traditional shoe laces if you want to use the latest scientific research to secure your sneakers.

Burkard Polster, a mathematician from Monash University, Australia, has published research into which type of shoe lacing is the most efficient in the journal Nature - the "most efficient" meaning the one that uses the least amount of lace. You might wonder why anyone apart from penny-pinching scrooges would be worried about wasting shoelace, but in fact the Shoelace problem is a restricted version of a much more famous mathematical conundrum - the Travelling salesman problem. This is the problem of finding the shortest route visiting all of a finite number of cities - which would obviously be of interest to any travelling salesmen trying to minimise their time on the road.

The Travelling salesman problem turns out to be much harder than it appears at first glance - just working out the distance for every possible route between 10 cities would mean 3,628,800 calculations! This is an active area of mathematical research, and none of the methods (known so far) of chosing a route finds the shortest route every time. You can see the latest research at the TSP site at Georgia Tech , including their result for a route touring 15,112 cities in Germany - the largest instance of the problem solved to date. [Editor's note 14/2/2023: This TSP site –http://www.tsp.gatech.edu/index.html – no longer exists.]

So what does all this mean for our humble shoe? "Given a single lace and a row of eyelets down each side of a shoe I wanted to find out the best ways of lacing shoes in a `reasonable manner', that is, a manner in which the shoelace visits all eyelets and every eyelet actually contributes towards pulling the two sides of the shoe together," Polster said. So just as in the Travelling salesman problem, where now instead of cities you have eyelets, you can consider which lacing is the shortest. But there are some restrictions on the route your lace takes if you don't want your expensive trainers to fall off. For any eyelet there is a segment of the lace that ends in that hole, and a segment that leaves that hole to go to another eyelet. For one of Polster's "reasonable" lacings, each eyelet has to have at least one of these segments connecting to the opposite column of eyelets, so that the lace at each eyelet is helping to pull the two sides of the shoe together.

Criss-cross lacing, straight-lacing and the controversial bow tie method

Polster had to consider all the possible lacings of a shoe - quite a task, considering that there are a staggering 51,840 for a shoe with just 5 eyelets on each side! So instead of brute force he used some powerful mathematical optimisation techniques to prove that the shortest "reasonable" lacing was not the more common criss-cross or straight-lacing, but instead a rarely used bow tie method. However this research probably won't have a revolutionary effect on how we tie our shoes, as Polster also calculated which lacing was the strongest , and this time these two traditional methods tied for the honour.

The travelling salesman problem has all sorts of applications, from the obvious, such as helping tourists taking a road trip to plan their shortest route and parcel pick-up companies to plan the most efficient route for drivers, to the more unexpected, such as telephone network routing and genome sequencing. It is even believed that monkeys intuitively solve this problem when gathering food. But at this time of the year, the one person who surely has the travelling salesman problem on his mind is Santa! Just what is the shortest route that visits every chimney in the world? Hmmm...