A semidefinite optimization approach to the target visitation problem
type: Item
instance of: scholarly article
title: A semidefinite optimization approach to the target visitation problem
zbMATH Open document ID: 1333.90151
published in: Optimization Letters
publication date: 2015-12-04T00:00:00Z
review text: 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.
reviewed by: Armin Hoffmann
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 90C56
zbMATH DE Number: 6516471
zbMATH Keywords: target visitation problem
zbMATH Keywords: linear ordering problem
zbMATH Keywords: traveling salesman problem
zbMATH Keywords: relaxation
zbMATH Keywords: semidefinite programming
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: interior point methods
zbMATH Keywords: bundle methods
author: Philipp Hungerländer
describes a project that uses: SeDuMi
describes a project that uses: Matlab
describes a project that uses: TSPLIB
describes a project that uses: Concorde
describes a project that uses: Biq Mac
MaRDI profile type: Publication
full work available at URL: s11590-014-0824-9
OpenAlex ID: W2004598396
cites work: Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
cites work: Q3425132
cites work: A Random Keys Based Genetic Algorithm for the Target Visitation Problem
cites work: Improved analysis of an algorithm for the coupled task problem with UET jobs
cites work: The linear ordering problem with cumulative costs
cites work: Q3320091
cites work: Q4821526
cites work: Semidefinite relaxations of ordering problems
cites work: Q4263707
cites work: On Semidefinite Programming Relaxations of the Traveling Salesman Problem
cites work: Geometry of cuts and metrics
cites work: Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
cites work: Induced binary probabilities and the linear ordering polytope: A status report
cites work: Some simplified NP-complete graph problems
cites work: Optimal Weighted Ancestry Relationships
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: The traveling salesman problem and its variations
cites work: An Interior-Point Method for Semidefinite Programming
cites work: Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
cites work: New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
cites work: A computational study and survey of methods for the single-row facility layout problem
cites work: 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
cites work: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
cites work: Assignment Problems and the Location of Economic Activities
cites work: A survey for the quadratic assignment problem
cites work: The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
cites work: A benchmark library and a comparison of heuristic methods for the linear ordering problem
cites work: Cooperative control and optimization
cites work: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
cites work: Q4537753
cites work: A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
cites work: The traveling salesman. Computational solutions for RSP applications
cites work: Handbook of semidefinite programming. Theory, algorithms, and applications
DOI: 10.1007/S11590-014-0824-9
description: scientific article; zbMATH DE number 6516471