Solving Euclidean Max-Sum problems exactly with cutting planes
This paper studies binary quadratic programs in which the objective is defined by the maximisation of a Euclidean distance matrix, subject to a general polyhedral constraint set. This class of nonconcave maximisation problems, which we refer to as the Euclidean Max-Sum problem, includes the capacita...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
2024
|
| Online Access: | http://purl.org/au-research/grants/arc/IC180100030 http://hdl.handle.net/20.500.11937/96034 |
| _version_ | 1848766078563385344 |
|---|---|
| author | Bui, Hoa Spiers, Sandy Loxton, Ryan |
| author_facet | Bui, Hoa Spiers, Sandy Loxton, Ryan |
| author_sort | Bui, Hoa |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | This paper studies binary quadratic programs in which the objective is defined by the maximisation of a Euclidean distance matrix, subject to a general polyhedral constraint set. This class of nonconcave maximisation problems, which we refer to as the Euclidean Max-Sum problem, includes the capacitated, generalised and max-sum diversity problems as special cases. Due to the nonconcave objective, traditional cutting plane algorithms are not guaranteed to converge globally. In this paper, we introduce two exact cutting plane algorithms to address this limitation. The new algorithms remove the need for a concave reformulation, which is known to significantly slow down convergence. We establish exactness of the new algorithms by examining the concavity of the quadratic objective in a given direction, a concept we refer to as directional concavity. Numerical results show that the algorithms outperform other exact methods for benchmark diversity problems (capacitated, generalised and max-sum), and can easily solve problems of up to three thousand variables. |
| first_indexed | 2025-11-14T11:45:26Z |
| format | Journal Article |
| id | curtin-20.500.11937-96034 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T11:45:26Z |
| publishDate | 2024 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-960342024-11-07T00:40:11Z Solving Euclidean Max-Sum problems exactly with cutting planes Bui, Hoa Spiers, Sandy Loxton, Ryan This paper studies binary quadratic programs in which the objective is defined by the maximisation of a Euclidean distance matrix, subject to a general polyhedral constraint set. This class of nonconcave maximisation problems, which we refer to as the Euclidean Max-Sum problem, includes the capacitated, generalised and max-sum diversity problems as special cases. Due to the nonconcave objective, traditional cutting plane algorithms are not guaranteed to converge globally. In this paper, we introduce two exact cutting plane algorithms to address this limitation. The new algorithms remove the need for a concave reformulation, which is known to significantly slow down convergence. We establish exactness of the new algorithms by examining the concavity of the quadratic objective in a given direction, a concept we refer to as directional concavity. Numerical results show that the algorithms outperform other exact methods for benchmark diversity problems (capacitated, generalised and max-sum), and can easily solve problems of up to three thousand variables. 2024 Journal Article http://hdl.handle.net/20.500.11937/96034 10.1016/j.cor.2024.106682 http://purl.org/au-research/grants/arc/IC180100030 https://creativecommons.org/licenses/by-nc/4.0/ fulltext |
| spellingShingle | Bui, Hoa Spiers, Sandy Loxton, Ryan Solving Euclidean Max-Sum problems exactly with cutting planes |
| title | Solving Euclidean Max-Sum problems exactly with cutting planes |
| title_full | Solving Euclidean Max-Sum problems exactly with cutting planes |
| title_fullStr | Solving Euclidean Max-Sum problems exactly with cutting planes |
| title_full_unstemmed | Solving Euclidean Max-Sum problems exactly with cutting planes |
| title_short | Solving Euclidean Max-Sum problems exactly with cutting planes |
| title_sort | solving euclidean max-sum problems exactly with cutting planes |
| url | http://purl.org/au-research/grants/arc/IC180100030 http://hdl.handle.net/20.500.11937/96034 |