Integer linear programming approaches to the blockmodel problem

Blockmodelling is a method for identifying structural similarities or equivalences between elements which has applications in a variety of contexts, including multiattribute performance assessment. One criterion for forming blocks results in a difficult non-linear integer program. We give several integer linear programming formulations of this problem and provide comparative computational results. We show that methods of reducing symmetry proposed by Sherali and Smith are not effective in this case and propose an iterative approach in which the size of the problem is reduced.