Quadratic convex reformulation for graph partitionning problems
Sourour Elloumi, Amélie Lambert · HAL - CNAM · 2013
Many graph partitionning problems can be formulated by quadratic programs (QP) with binary variables and linear and quadratic constraints. We apply the general approach that consists in first reformulating the initial (QP) into an equivalent program (QP ). Problem (QP ) has the additional property that its continuous relaxation is a convex quadratic problem. It can then be solved by branch-and-bound based on quadratic convex relaxation. We show how variants of thisgeneral approach perform on many graph partitionning problems.