Touring Convex Bodies - A Conic Programming Solution.
Valentin Polishchuk, Joseph S. B. Mitchell · 2005
We study the problem of finding a shortest tour visiting a given sequence of convex bodies in R d. To our knowledge, this is the first attempt to attack the problem in its full generality: we investigate high-dimensional cases (d ≥ 2); we consider convex bodies bounded by (hyper)planes and/or (hyper)spheres; we do not restrict the start and the goal positions of the tour to be single points, we measure the length of the tour according to either Euclidean or L1 metric. Formulating the problem as a second order cone program (SOCP) makes it possible to incorporate distance constraints, which cannot be handled by a purely geometric algorithm. We implemented the SOCP in MATLAB and obtained its solution with the SeDuMi package. We ran computational experiments, which suggest that the proposed solution is practical. Finally, we present NP-hardness results, showing that the assumptions we make in the statement of our problems are crucial for the problems to be tractable.