A semidefinite optimization approach to the target visitation problem (Q895779)

The target visitation problem (TVP) is exactly described by an semidefinite optimization problem with variables in \(\{-1,1\}\) (Theorem 3) as special quadratic position problem. Five sophisticated relaxations are derived by dropping the integrality condition and having different problem reductions. The upper bounds of the original problem given by exact solutions of the relaxations are computed for small and medium problems by the interior point software SeDuMi of Matlab\(^{TR}\) [\textit{J. F. Sturm}, Optim. Methods Softw. 11--12, No. 1--4, 625--653 (1999; Zbl 0973.90526)]. Feasible tours are derived from this relaxations by some heuristics. For large instances bundle methods are used for getting the solution of the relaxed problems. They show in a lot of Benchmark tests that the proposed semidefinite relaxations together with heuristics creates results being much closer to the solution as the integer programming models and heuristics used in (see [\textit{A. Hildenbrandt}, The target visitation problem. Heidelberg: Univ. Heidelberg, Naturwissenschaftlich-Mathematische Gesamtfakultät (Diss.) (2015; Zbl 1322.90050)]) especially for TVP with large scale instances.