New integer linear programming formulations for the maximally diverse grouping problem
摘要
The Maximally Diverse Grouping Problem (MDGP) is the problem of assigning a set of elements to mutually disjoint groups in order to maximise the overall diversity between the elements. The MDGP is often formulated as an Integer Quadratic Programme (IQP). Because the MDGP is NP-complete, most studies have focused on heuristic solution approaches, as compared to exact solution approaches, to the problem. Although heuristic solution approaches are often used in practice, these approaches do not guarantee a global optimal solution. Conversely, although exact solution approaches are not often used in practice, these approaches guarantee a global optimal solution, and therefore serve as useful benchmarks for the performance of heuristics. As such, a few studies have formulated the MDGP as an Integer Linear Programme (ILP), which can be solved using exact solution approaches. The present paper proposes two new ILP formulations, and compares their performances against existing formulations. The proposed formulations can be used to establish useful benchmarks for the performance of heuristics in a broader range of applications moving forward.