On Semidefinite Programming Relaxations of Association Schemes with Application to Combinatorial Optimization Problems

We construct convex, semidefinite programming (SDP) relaxations of the convex hull of association schemes with given parameters. As an application, we obtain new and known SDP relaxations of several combinatorial optimizations problems, including the traveling salesman and cycle covering problems (by considering the Lee association scheme) and the maximum p-section problem (by considering the scheme of the complete p-partite graph). Thus, the approach in this paper may be seen as a unified framework to generate SDP relaxations of various combinatorial optimization problems