The most famous problem in Operations Research is probably the Traveling Salesman Problem $($TSP$).$ We are given several cities and the distances between them, and our goal is to construct the minimum distance $($or cost$)$ route $($or tour$)$ that begins and ends at the same place and visits each required city along the way.

Many network problems can be solved by creating linear programming $($LP$)$ formulations. TSP cannot, but there are LPs that provide helpful relaxations. One formulation that might at first appear to be sufficient is given below:

Let x$\_($i$,$j$)=\{(1,$if the tour includes the arc connecting city i to city j@$0,$ otherwise$)$

Our LP relaxation is as follows

Min Z$=\_($j$=$i$+1)^$n$\_($i$=1)^($n$-1)$c$\_($i$,$j$)$ x$\_($i$,$j$)$

s$.$t$.\_($k$=1)^($i$-1)$x$\_($k$,$i$)+\_($j$=$i$+1)^$n$$x$\_($i$,$j$)=2$ for all city i$^\text{'}$ s

all x$\_($i$,$j$)>=0$

Essentially, the constraint ensures that we must take an arc into each city and out of each city so that our tour both visits and leaves each city.