# Lehigh ISE / COR@L Lab Wiki

### Site Tools

travelling_salesman_problem

# Differences

This shows you the differences between two versions of the page.

 travelling_salesman_problem [2015/09/22 12:49]bsuresh Minor change, added \ldots travelling_salesman_problem [2018/10/01 13:29] (current)bsuresh old revision restored (2017/04/05 23:01) Both sides previous revision Previous revision 2018/10/01 13:29 bsuresh old revision restored (2017/04/05 23:01)2017/04/18 00:18 tramo5 2017/04/05 23:01 sertalpbilal old revision restored (2015/10/28 11:30)2017/03/27 05:59 ntcnet [Computational complexity] 2015/10/28 11:30 sertalpbilal 2015/09/22 12:58 bsuresh old revision restored (2015/09/22 12:50)2015/09/22 12:58 bsuresh deleted for testing2015/09/22 12:50 bsuresh old revision restored (2014/09/23 22:48)2015/09/22 12:49 bsuresh Minor change, added \ldots2014/09/23 22:48 sertalpbilal 2014/09/23 19:21 sertalpbilal old revision restored (2014/09/23 12:24)2014/09/23 19:20 sertalpbilal 2014/09/23 12:24 sertalpbilal created Next revision Previous revision 2018/10/01 13:29 bsuresh old revision restored (2017/04/05 23:01)2017/04/18 00:18 tramo5 2017/04/05 23:01 sertalpbilal old revision restored (2015/10/28 11:30)2017/03/27 05:59 ntcnet [Computational complexity] 2015/10/28 11:30 sertalpbilal 2015/09/22 12:58 bsuresh old revision restored (2015/09/22 12:50)2015/09/22 12:58 bsuresh deleted for testing2015/09/22 12:50 bsuresh old revision restored (2014/09/23 22:48)2015/09/22 12:49 bsuresh Minor change, added \ldots2014/09/23 22:48 sertalpbilal 2014/09/23 19:21 sertalpbilal old revision restored (2014/09/23 12:24)2014/09/23 19:20 sertalpbilal 2014/09/23 12:24 sertalpbilal created Line 1: Line 1: ====== Travelling salesman problem ====== ====== Travelling salesman problem ====== + + <​note>​This is a playground page for new users. Feel free to edit here!​ The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization,​ important in operations research and theoretical computer science. The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization,​ important in operations research and theoretical computer science. Line 5: Line 7: ===== Integer linear programming formulation ===== ===== Integer linear programming formulation ===== - TSP can be formulated as an integer linear program. Label the cities with the numbers $0, \ldots, n$ and define: + TSP can be formulated as an integer linear program. Label the cities with the numbers $0, ..., n$ and define:  ​x_{ij} = \begin{cases} 1 & \text{the path goes from city } i \text{ to city } j \\ 0 & \text{otherwise} \end{cases} ​x_{ij} = \begin{cases} 1 & \text{the path goes from city } i \text{ to city } j \\ 0 & \text{otherwise} \end{cases}