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.
| Type : | : | Présentation orale (résumé seul indiquant : problématique + méthodologie + contributions) |
| Langue du texte intégral | : | anglais |
| Thématiques | : | Graphes, flots, algorithmes combinatoires et approximation |
| Mots-Clés | : | Vertex Separator Problem ; semidefinite programming relaxation ; variable neighborhood search |
| PDF version | : |  PDF version |
