The symmetric traveling salesman problem (STSP) is to find a minimum weight Hamiltonian cycle in a weighted complete graph on n nodes. One direction which seems promising for finding improved solutions for the STSP is the study of a linear relaxation of this problem called the subtour elimination problem (SEP). A well–known conjecture in combinatorial optimization says that the integrality gap of the SEP is 4/3 in the metric case. Finding the exact value for this integrality gap is challenging even for small values of n as it is difficult to model this problem in a way that can be solved practically. We describe how we are able to overcome such difficulties and obtain the exact integrality gap for all values of n up to 10 and a lower bound for this gap for all values of n from 11 to 14. Our results give rise to a new stronger form of the conjecture which is dependent on n.
