A semidefinite optimization approach to the target visitation problem (Q895779)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A semidefinite optimization approach to the target visitation problem |
scientific article |
Statements
A semidefinite optimization approach to the target visitation problem (English)
0 references
4 December 2015
0 references
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.
0 references
target visitation problem
0 references
linear ordering problem
0 references
traveling salesman problem
0 references
relaxation
0 references
semidefinite programming
0 references
combinatorial optimization
0 references
interior point methods
0 references
bundle methods
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references