A semidefinite optimization approach to the target visitation problem
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.
- 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
- A benchmark library and a comparison of heuristic methods for the linear ordering problem
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- A computational study and survey of methods for the single-row facility layout problem
- A random keys based genetic algorithm for the target visitation problem
- A survey for the quadratic assignment problem
- An Interior-Point Method for Semidefinite Programming
- Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Assignment Problems and the Location of Economic Activities
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Cooperative control and optimization
- Geometry of cuts and metrics
- Handbook of semidefinite programming. Theory, algorithms, and applications
- scientific article; zbMATH DE number 3850790 (Why is no real title available?)
- scientific article; zbMATH DE number 1342125 (Why is no real title available?)
- scientific article; zbMATH DE number 1757965 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- Improved analysis of an algorithm for the coupled task problem with UET jobs
- Induced binary probabilities and the linear ordering polytope: A status report
- New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
- On Semidefinite Programming Relaxations of the Traveling Salesman Problem
- Optimal Weighted Ancestry Relationships
- Semidefinite relaxations of ordering problems
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Some simplified NP-complete graph problems
- The linear ordering problem with cumulative costs
- The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
- The traveling salesman problem and its variations
- The traveling salesman problem. A computational study.
- The traveling salesman. Computational solutions for RSP applications
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- The target visitation arc routing problem
- A branch-and-cut algorithm for the target visitation problem
- scientific article; zbMATH DE number 1873286 (Why is no real title available?)
- The target visitation problem
- A linear ordering problem with weighted rank
- New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
- Lifted formulations for the target visitation problem
This page was built for publication: A semidefinite optimization approach to the target visitation problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q895779)
