Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps.
Samuel C. GutekunstDavid P. WilliamsonPublished in: CoRR (2019)
Keyphrases
- traveling salesman problem
- semidefinite programming
- semidefinite
- linear programming
- linear programming relaxation
- valid inequalities
- lp relaxation
- combinatorial optimization
- quadratically constrained quadratic
- ant colony optimization
- interior point methods
- mixed integer
- linear program
- feasible solution
- primal dual
- integer programming
- kernel matrix
- optimization problems
- column generation
- maximum margin
- knapsack problem
- dynamic programming
- lower bound
- traveling salesman
- optimal solution
- neural network
- metaheuristic