Quadratic Convex Reformulation for Graph Partitionning Problems

Sourour Elloumi^* and Amélie Lambert

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 this general approach perform on many graph partitionning problems.

Mathematics Subject Classification: 90C20 90C11 90C27

Keywords: Quadratic programming ; integer programming ; graph partitionning

Minisymposion: Algorithms Based on Semidefinite Optimization