Different formulations for solving the heaviest k-subgraph problem

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 of different MP formulations of HSP. Computational experiments when the weight of each edge is equal to 1 are reported. They show that the MIP approach is particularly efficient for dense instances.