My father is coming to visit Singapore next week. Of course one thing I have to do is take him to sample some of the great food at the hawker centres here. Say we are very ambitious and want to visit 18 of the best hawker centres on the island…in order to intelligently engage in the raging debate on which stall has the best char kway teow. As my Dad’s stay is limited, we want the shortest tour visiting all these hawker centres.

Here is a google map of the 18 chosen hawker centres. What do you think the shortest tour is?

This is an instance of the traveling salesman problem (TSP), the most celebrated problem in computer science. Easy to state and visualize, it has a catchy story to boot: a salesman wants to visit a set of cities and return to his starting point. What is the shortest tour possible?

TSP is an NP-hard problem and we do not know of any efficient way to solve it in general. In this post, I will talk about some algorithmic approaches using linear programming, and use them to find the shortest hawker tour for our example.

The algorithms that have been developed for TSP are very impressive, and optimal tours have been found for real-life questions involving hundreds of thousands of cities.

We will content ourselves with the the 1954 state of the art, following the approach Dantzig, Fulkerson, and Johnson used to solve a 49-city TSP problem of cities in the US. This was by far the largest problem solved at the time—remember they did this without a computer! This paper introduced the cutting-plane method, which has been extremely influential not just for TSP but many optimization problems.

Say we have a vector \(c_{i,j}\) indicating the distance between city \(i\) and \(j\). We assume that the distance between city \(i\) and \(j\) is the same as between \(j\) and \(i\), so this will be a vector of length \(n \choose 2\), and I will refer to entries of \(c\) with indices \(i < j\). In the hawker example, I used distances from Google maps driving distances. These distances are not actually symmetric due to one way streets and the like, so I first symmetrized the distances.

We can also encode a tour as a boolean vector \(x_{i,j}\) with \(i < j\) where \(x_{i,j}=1\) if the tour goes from city \(i\) to city \(j\) and is \(0\) otherwise. Thus the total cost is \(c^t x\).

The full TSP optimization problem can thus be written as

\[ \begin{aligned} \mbox{minimize} & c^t x \\ &x \in S \end{aligned}\]

where \(S\) is the set of all valid tours. The set \(S\) of all tours is pretty complicated, and we do not know how to efficiently optimize over it. So we instead consider a problem we can solve: optimizing the same objective function subject to constraints given by linear inequalities \(Ax \le b\), resulting in a linear program

\[ \begin{aligned} \mbox{minimize} & c^t x \\ & Ax \le b \end{aligned}\]

We want this linear program to be a relaxation of TSP meaning that we should choose constraints such that \(\{x:Ax \le b\}\) contains the set of valid tours \(S\). One property that any tour \(x \in S\) must satisfy is that \(\sum_{j} x_{i,j}=2\), that is every vertex has degree 2. This is the basic relaxation that Dantzig, Fulkerson, and Johnson start with:

\[ \begin{aligned} \mbox{minimize} & c^t x \\ & \sum_{j} x_{i,j}=2 \mbox{ for all } i \\ & x \ge 0 \end{aligned}\]

In the hawker problem, we get the following solution to this linear program. Luckily, the solution turns out to be integral and so it is easy to draw it on the map.

Here is what the solution does in Chinatown

This solution has several problems. First off, there are double lines, \(x_{i,j} =2\), which never happens in a true tour. Secondly, this solution has small cycles like we see here in Chinatown, also not possible in a true tour. Here is where the cutting-plane method comes in. We add linear constraints, violated by this solution but true for any tour, in order to eliminate this spurious solution. To address the first fault of this solution we can add what are known as degree constraints that \(x_{i,j} \le 1\). If there are \(n\) cities there are \(O(n^2)\) many such constraints so we could add all of them and still have a polynomial size linear program. For the second problem we add what are known as subtour constraints. These constraints say that for any subset \(T\) of hawker centres (not including all of them), \(\sum_{i<j \in T} x_{i,j} \le |T|-1\). This is another constraint you can see will be satisfied by any true tour. Notice that there are exponentially many subtour constraints, one for each subset of cities.

Following Dantzig, Fulkerson, and Johnson—who after all were reasoning about these linear programs by hand—we try to eliminate false tours by adding just a few strategic constraints of the above two types. The east (Changi Village) and west (Ghim Moh) outlying hawker centres both have double edges in the first solution. This is fairly natural as the second closest city to each of these is much further away than the closest one. We add degree constraints to eliminate these double lines. We also add a degree constraint in Chinatown between Amoy St and Lau Pa Sat. Notice that in the first solution there is not even a double edge here, but it pops up later on so we squash it now.

When we solve the linear program with these degree constraints added, the solution fortunately again has integral weights so it is easy to draw. But we are not lucky enough to get a tour yet.

In Chinatown there is still a double edge between Chinatown Complex and Hong Lim, and a triangle between Maxwell Road, Amoy St, and Lau Pa Sat, which are all very close together.

Now we start adding constraints to eliminate some of these subtours. We add constraints to kill the triangle you see on the west side between Ghim Moh, ABC Brickhouse, and Tiong Bahru. We also kill the east side triangle between Changi Village, East Coast Lagoon, and Tampines Round Market. Finally, we kill the Chinatown triangle between Maxwell Road, Amoy St, and Lau Pa Sat.

With these 3 additional constraints added, the minimum cost solution is no longer integral, but all edges have weight either 1 or 1/2 (or zero). In the pictures below the thick lines represent edges of weight 1 and the thin lines edges of weight 1/2.

And things get interesting in Chinatown…

What can we identify that is wrong with this solution? An equivalent way to phrase the subtour constraints \(\sum_{i,j \in T} x_{i,j} \le |T|-1\), saying that there cannot be too many edges within a set, is that there must be at least two edges leaving any set (that does not contain all the vertices). The picture below shows two sets which violate this constraint—each only has edges of total weight 1 leaving the set.

If we add these two subtour constraints our optimization returns a true tour! In total we wound up using 26 constraints for the 18 hawker tour. To solve the linear programs I used the freely available software Octave. If you want to try it yourself, the code is available on github.

[...] a previous post, we solved a small instance of the traveling salesman problem (TSP) around Singapore’s hawker [...]

I recently found many useful information in your website especially this blog page. Among the lots of comments on your articles. Thanks for sharing.

how to get views on youtube fast

This was really an interesting topic and I kinda agree with what you have mentioned here!

youtube views

transfert vhs

You know your projects stand out of the herd. There is something special about them. It seems to me all of them are really brilliant!

Thank you very much for the sharing! COOL..

Im no expert, but I believe you just made an excellent point. You certainly fully understand what youre speaking about, and I can truly get behind that.

Design Craft Exhibition

This is a brilliant blog! I’m very happy with the comments!..

discount codes

I’ve been searching for some decent stuff on the subject and haven’t had any luck up until this point, You just got a new biggest fan!..

vouchers codes

Great survey, I’m sure you’re getting a great response.

seo new york

Thank you for some other informative blog. Where else could I get that type of information written in such an ideal means? I have a mission that I’m just now working on, and I have been at the look out for such information.

Commission Black Ops review

Singapore is the great place and I love to visit it again and again.

Total Curve Herbal Breast Pills

Thanks for the good information you give them.

My father visited Singapore and he tell me this is the great place in Asia.

That is a really good tip particularly to those new to the blogosphere. Short but very accurate info… Many thanks for sharing this one. A must read post!

This is a very well written and useful article. keep up the good work

It is great to see your father chooses Singapore for his journey.

The way you write your articles is just mindblowing. Without a doubt, there is not a single person better at this job than you right now. Keep giving the great stuff. here are the findings

I am always searching online for articles that can help me. There is obviously a lot to know about this. I think you made some good points in Features also. Keep working, great job!Steven Wyer

Singapore is the great place and I am glad your father chooses Singapore to start his journey. Erectile Dysfunction Conqueror Review

That is a really good tip particularly to those new to the blogosphere. Short but very accurate info… Many thanks for sharing this one. A must read post!blood thinning medicine lawsuit

That is a really good tip particularly to those new to the blogosphere. Short but very accurate info… Many thanks for sharing this one. A must read post! cheap futons

I really believe the reality with this consider that You have the efficiency of modifying in that way, that soon Your blog site web page will be the most research of everyone. Now my friends appreciate Your career.

I love Singapore and love to visit it again and again.

Love what you’re doing here guys, keep it up!..

his comment is here

There I found your blog using msn This is a really well written article Ill make sure to bookmark it and return to read more of your useful information Thanks for the post I will definitely comeback. Andrew

admit, I have not been on this web page in a long time… however it was another joy to see It is such an important topic and ignored by so many, even professionals. professionals. I thank you to help making people more aware of possible issues. look at here now

I am always searching online for articles that can help me. There is obviously a lot to know about this. I think you made some good points in Features also. Keep working, great job!Lords mobile hack

Great info. I love all the posts, I really enjoyed, I would like more information about this, because it is very nice. Thanks for sharing. dog insurance

That is a really good tip particularly to those new to the blogosphere. Short but very accurate info… Many thanks for sharing this one. A must read post! male enhancement pills

I’m excited to uncover this page. I need to to thank you for ones time for this particularly fantastic read!! http://www.freeangrybirdsgame.org

professionals. I thank you to help making people more aware of possible issues.https://www.hirerush.com/TX:Austin/service/concrete-contractors

I have understood everything in this article, and I need more on this to complete my study on the topic, thanks to provide such nice details. app developers

Love what you’re doing here guys, keep it up!.. clash royale cheat

Useful info. Lucky me I discovered your web site by accident, and I am stunned why this accident didn’t took place earlier! I bookmarked it. broken iphone repair