Touring convex bodies - A conic programming solution

We study the problem of finding a shortest tour visiting a given sequence of convex bodies in Rd. To our knowl- edge, 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 pos- sible to incorporate distance constraints, which cannot be handled by a purely geometric algorithm. We implemented the SOCP in MATLAB and ob- tained its solution with the SeDuMi package. We ran computational experiments, which suggest that the pro- posed solution is practical. Finally, we present NP-hardness results, showing that the assumptions we make in the statement of our prob- lems are crucial for the problems to be tractable.