An exact cutting plane method for the Euclidean max-sum diversity problem
This paper aims to answer an open question recently posed in the literature, that is to find a fast exact method for solving the max-sum diversity problem, a nonconcave quadratic binary maximization problem. We show that, for Euclidean max-sum diversity problems (EMSDP), the distance matrix defining...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
2023
|
| Online Access: | http://purl.org/au-research/grants/arc/IC180100030 http://hdl.handle.net/20.500.11937/96042 |
| _version_ | 1848766080960430080 |
|---|---|
| author | Spiers, Sandy Bui, Hoa Loxton, Ryan |
| author_facet | Spiers, Sandy Bui, Hoa Loxton, Ryan |
| author_sort | Spiers, Sandy |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | This paper aims to answer an open question recently posed in the literature, that is to find a fast exact method for solving the max-sum diversity problem, a nonconcave quadratic binary maximization problem. We show that, for Euclidean max-sum diversity problems (EMSDP), the distance matrix defining the quadratic term is always conditionally negative definite. This interesting property ensures that the cutting plane method is exact for (EMSDP), even in the absence of concavity. As such, the cutting plane method, which is 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 is capable of solving two-coordinate problems of up to eighty-five thousand variables. |
| first_indexed | 2025-11-14T11:45:28Z |
| format | Journal Article |
| id | curtin-20.500.11937-96042 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T11:45:28Z |
| publishDate | 2023 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-960422024-11-08T01:26:43Z An exact cutting plane method for the Euclidean max-sum diversity problem Spiers, Sandy Bui, Hoa Loxton, Ryan This paper aims to answer an open question recently posed in the literature, that is to find a fast exact method for solving the max-sum diversity problem, a nonconcave quadratic binary maximization problem. We show that, for Euclidean max-sum diversity problems (EMSDP), the distance matrix defining the quadratic term is always conditionally negative definite. This interesting property ensures that the cutting plane method is exact for (EMSDP), even in the absence of concavity. As such, the cutting plane method, which is 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 is capable of solving two-coordinate problems of up to eighty-five thousand variables. 2023 Journal Article http://hdl.handle.net/20.500.11937/96042 10.1016/j.ejor.2023.05.014 http://purl.org/au-research/grants/arc/IC180100030 https://creativecommons.org/licenses/by-nc-nd/4.0/ fulltext |
| spellingShingle | Spiers, Sandy Bui, Hoa Loxton, Ryan An exact cutting plane method for the Euclidean max-sum diversity problem |
| title | An exact cutting plane method for the Euclidean max-sum diversity problem |
| title_full | An exact cutting plane method for the Euclidean max-sum diversity problem |
| title_fullStr | An exact cutting plane method for the Euclidean max-sum diversity problem |
| title_full_unstemmed | An exact cutting plane method for the Euclidean max-sum diversity problem |
| title_short | An exact cutting plane method for the Euclidean max-sum diversity problem |
| title_sort | exact cutting plane method for the euclidean max-sum diversity problem |
| url | http://purl.org/au-research/grants/arc/IC180100030 http://hdl.handle.net/20.500.11937/96042 |