Recent advances in solving some optimization problems in graphs by quadratic programming
Sourour Elloumi, Amélie Lambert
Abstract
We review Quadratic Convex Reformulation (QCR) for quadratic pro-grams with general integer variables. This solution 2-phase approachconsist in first reformulating the quadratic program into an equivalentother problem having a convex ob jective function. The second phaserelies on MIP solvers that solve the reformulated problem by standardbranch-and-b ound. Then, we consider some graph partitioning problemsthat can be formulated as quadratic programs with binary variables. Weshow many enhancements of the standard QCR method that efficientlysolve graph partitioning problems