Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps.
Samuel C. GutekunstDavid P. WilliamsonPublished in: Math. Oper. Res. (2022)
Keyphrases
- traveling salesman problem
- semidefinite programming
- semidefinite
- linear programming
- linear programming relaxation
- valid inequalities
- lp relaxation
- quadratically constrained quadratic
- combinatorial optimization
- interior point methods
- primal dual
- ant colony optimization
- integer programming
- linear program
- optimization problems
- kernel matrix
- np hard
- traveling salesman
- mixed integer
- maximum margin
- crossover operator
- lower bound
- column generation
- branch and bound
- feasible solution
- special case
- convex relaxation
- kernel function