A semidefiinite programming relaxation for Vertex Separator Problem

Chuan Xu (1) , Abdel Lisser (1) , Rendl Frenz (2, 3)

1 LRI - Laboratoire de Recherche en Informatique
2 Universität Klangenfurt
3 Department of Mathematics

Vertex Separator Problem (VSP for short) is a well known NP complete graph problem. VSP consists in separating the graph into k parts of the same size. In this talk, we firstly propose an integer programming formulation for VSP in the case where k=2, and use the commercial solver CPLEX to obtain optimal solutions for small instances, i.e., graph with less than 125 nodes. Then, we introduce an efficient semidefinite programming relaxation (SDP for short). We solve the SDP relaxation by using the bundle method. We also propose an efficient variant of variable neighborhood search (VNS for short) to obtain feasible solutions. We combine both SDP and VNS to come up with good feasible solutions. Our numerical results show that our SDP model provides a good starting point for VNS which leads to results comparable with the best literature ones for graphs with up to 2000 nodes.

Mots clés: Vertex Separator Problem; semidefinite programming relaxation; variable neighborhood search

Domaines: Recherche opérationnelle [math.OC]

Chuan Xu, Abdel Lisser, Rendl Frenz. A semidefiinite programming relaxation for Vertex Separator Problem. ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, Société française de recherche opérationnelle et d'aide à la décision, Feb 2014, Bordeaux, France. ⟨hal-00946499⟩