Solutions to the Traveling Salesman Problem (TSP) are known to come from permutation matrices (in the asymmetric case) and adjacency matrices (in the symmetric case). With this knowledge, we propose an alternative formulation of the subtour elimination constraints that is based on eigenvalues and eigenvectors of permutation and adjacency matrices. Both SDP and non-SDP formulations of this approach will be discussed. Comparisons to existing methods will be explored, and potential paths for future improvement will be identified.

We present a computational study of SDP-based bounds for Max-Cut and k-cluster problems that use rounded psd inequalities as cutting planes to strengthen the basic relaxation. These are a subset of the gap inequalities introduced by Laurent and Poljak. We propose a fast optimization algorithms to efficiently separate violated rounded psd inequalities and use the augmented Lagrangian method as a bounding routine. Two simple and effective heuristics based on the greedy algorithm and a variation of the alternating direction method of multipliers (ADMM) are presented. Our numerical experiments show that our approach is very efficient in finding cutting planes with large violation and provide strong upper bounds in practice.

Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two variants of exact algorithms using semidefinite programming (SDP) to compute this constant for any graph. The first variant uses the SDP relaxation first to reduce the search space considerably. One implementation of this variant applies then an SDP-based branch-and-bound algorithm, along with heuristic search.
The second implementation transforms the problem into an instance of a max-cut problem and solves this using the state-of-the-art solver BiqBin.

Our second variant to compute the edge expansion uses Dinkelbach's algorithm for fractional programming, again, using tools from semidefinite programming.

To the best of our knowledge, these are the first SDP-based solvers for computing the edge expansion of a graph.

A standard technique for bounding a combinatorial optimization problem is to form a semidefinite relaxation of the problem by “lifting” the problem into a higher dimensional space of symmetric matrices. For some combinatorial problems such as maximum k-cluster, the resulting semidefinite relaxation is not strictly feasible. In the context of the maximum k-cluster problem, we present an equivalent, strictly feasible semidefinite relaxation by way of facial reduction. We provide a recipe to form this semidefinite relaxation directly, bypassing the lifting and facial reduction steps entirely. We then present our work on generalizing this result, and provide a recipe for constructing a strictly feasible semidefinite relaxation of binary quadratic problems with a single linear constraint with non-zero right-hand side. In addition, we also present numerical results that support the inclusion of facial reduction in the binary quadratic solver BiqCrunch, as well as results supporting the use of facial reduction when solving a semidefinite relaxation of the maximum k-cluster problem.