An exact algorithm for the Minimum Gap Graph Partitioning Problem
针对最小间隙图划分问题，提出基于扩展整数线性规划的两种松弛方法，通过分支机制在多项式候选变量上搜索，实验表明可求解最多300个顶点的实例。
The Minimum Gap Graph Partitioning Problem requires to divide a vertex-weighted undirected graph into a given number of vertex-disjoint connected components, such that the sum of the maximum weight differences over all components is minimized. Based on an extended Integer Linear Programming formulation with an exponential number of binary variables, we propose two relaxations that exploit the properties of the objective function so as to restrict the search for the optimal solution to a polynomial subset of variables. We also introduce a branching scheme that maintains this nice property in all subproblems for both relaxations. This allows to replace the pricing mechanism, typically adopted to manage extended formulations, with a branching mechanism on a polynomial number of candidate variables. The experimental results show that both approaches can solve to optimality instances up to 300 vertices, unless very sparse and with a large number of subgraphs, and determine tight optimality gaps on the unsolved ones, if supported by an effective metaheuristic.