This talk is partitioned into two parts.

In the first part we consider two applications of the traveling salesman problem (TSP). We start by considering the structure learning of Bayesian networks, an important problem that arises in numerous machine learning and uncertainty quantification settings. We present a novel approach for learning the structure of Bayesian networks using the solution of an appropriately constructed TSP. In our approach, one computes an optimal ordering (partially ordered set) of random variables using methods for the TSP. This ordering significantly reduces the search space for the subsequent greedy optimization that computes the final structure of the Bayesian network. We demonstrate our approach of learning Bayesian networks on publicly available datasets. For the second application, we consider a problem in which a large number of moving targets must be intercepted by a single agent as quickly as possible. Decision-making about which target to pursue next is driven by the repeated heuristic solution of the TSP, which is compared to a greedy algorithm over different problem parameterizations. The proposed method is superior when the targets move at low speeds, and its relative performance improves as sensor noise worsens.

In the second part, we present a novel heuristic approach for computing the solution of the TSP. We relax the TSP to the Procrustes problem and compute the resulting optimal solution. We then construct a homotopy between the solution of the Procrustes problem and the distance matrix to improve the original solution. The solution of the homotopy is then used to bias the Lin-Kernighan approach. We find that this approach provides significant improvement over the standard approach of using minimum spanning trees. In particular, for randomly generated TSPs, our approach is found to find lower cost solutions in 85% of the problems. For TSPLIB challenge problems, we find lower cost solutions in nearly all tested examples.