A semidefinite optimization approach to the target visitation problem

DOI10.1007/s11590-014-0824-9zbMath1333.90151OpenAlexW2004598396MaRDI QIDQ895779

Philipp Hungerländer

Publication date: 4 December 2015

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-014-0824-9

zbMATH Keywords

semidefinite programmingcombinatorial optimizationrelaxationtraveling salesman probleminterior point methodsbundle methodslinear ordering problemtarget visitation problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Derivative-free methods and methods using generalized derivatives (90C56) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

The target visitation arc routing problem, A linear ordering problem with weighted rank, New semidefinite programming relaxations for the linear ordering and the traveling salesman problem, A branch-and-cut algorithm for the target visitation problem

Uses Software

• Matlab
• TSPLIB
• SeDuMi
• Concorde
• Biq Mac

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A computational study and survey of methods for the single-row facility layout problem
• Semidefinite relaxations of ordering problems
• A benchmark library and a comparison of heuristic methods for the linear ordering problem
• The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
• Cooperative control and optimization
• New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• A survey for the quadratic assignment problem
• Improved analysis of an algorithm for the coupled task problem with UET jobs
• Induced binary probabilities and the linear ordering polytope: A status report
• Some simplified NP-complete graph problems
• The traveling salesman. Computational solutions for RSP applications
• The traveling salesman problem and its variations
• The linear ordering problem with cumulative costs
• Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
• Assignment Problems and the Location of Economic Activities
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• A Random Keys Based Genetic Algorithm for the Target Visitation Problem
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Optimal Weighted Ancestry Relationships
• 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• An Interior-Point Method for Semidefinite Programming
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Geometry of cuts and metrics