Page History

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

.