Question

1. Write down the entire polynomial-size formulation for Asymmetric Travelling Salesman Problem

2. Explain the constraints and the variables, and HOW the polynomially many constraints work in eliminating subtours.

Answer 1

Let a graph G = (V, E) be a given complete digraph, where V is a vertices V={1,…,n} is the vertex set and E={(i,j):i,j∈V} is the arc set, and let c _ij be the cost associated with arc (i,j)∈E (with cii=+∞ for i∈V).

A Hamiltonian circuit (tour) of G is a circuit visiting each vertex of Vexactly once. The Asymmetric Traveling Salesman Problem (ATSP) is to find a Hamiltonian circuit G∗=(V,E∗) of G whose cost ∑(i,j)∈A∗cij is minimum..

The polynomial formulations can be directly solved by a general-purpose ILP solver.

The earliest polynomial formulation of the ATSP is owed to Miller (1960) (hereafter MTZ)

ui−uj+(n−1)xij ≤ n−2,i,j=2,…,n;

where ui,i=2,…,n,ui,i=2,…,n, is an arbitrary real number representing the order of vertex i in the optimal tour, and constraints (10) break subtours.