Different Formulations for Solving the HeaviestK-Subgraph Problem
Alain Billionnet · INFOR Information Systems and Operational Research · 2005
We consider the heaviest k-subgraph problem (HSP), i.e. determine a block of k nodes of a weighted graph (of n nodes) such that the total edge weight within the subgraph induced by the block is maximized. The aim of the paper is to show what can be expected from mixed-integer linear programming for solving this problem. We compare from a theoretical and practical point of view different MIP formulations of HSP. Computational experiments when the weight of each edge is equal to I are reported. They show that the MIP approach is particularly efficient for dense instances.