Santiago, Chile

Talk given at IFORS 2023 https://ifors2023.com/ 

Abstract:

This research answers an open question recently posed in the literature - to find a fast exact method for solving the max-sum diversity problem, a nonconcave quadratic binary maximization problem. For Euclidean max-sum diversity problems (EMSDP), the distance matrix defining the quadratic term is always conditionally negative definite. This interesting property ensures the cutting plane method is exact for EMSDP, even in the absence of concavity. The cutting plane method, primarily designed for concave maximisation problems, converges to the optimal solution of EMDSP. The method was evaluated on several standard benchmark test sets, where it was shown to outperform other exact solution methods for EMSDP, and can solve two-coordinate problems of up to eighty-five thousand variables.