Solving Euclidean Max-Sum problems exactly with cutting planes
dc.contributor.author | Bui, Hoa | |
dc.contributor.author | Spiers, Sandy | |
dc.contributor.author | Loxton, Ryan | |
dc.date.accessioned | 2024-10-08T05:03:26Z | |
dc.date.available | 2024-10-08T05:03:26Z | |
dc.date.issued | 2024 | |
dc.identifier.citation | Bui, H.T. and Spiers, S. and Loxton, R. 2024. Solving Euclidean Max-Sum problems exactly with cutting planes. Computers and Operations Research. 168. | |
dc.identifier.uri | http://hdl.handle.net/20.500.11937/96034 | |
dc.identifier.doi | 10.1016/j.cor.2024.106682 | |
dc.description.abstract |
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. | |
dc.relation.sponsoredby | http://purl.org/au-research/grants/arc/IC180100030 | |
dc.rights.uri | https://creativecommons.org/licenses/by-nc/4.0/ | |
dc.title | Solving Euclidean Max-Sum problems exactly with cutting planes | |
dc.type | Journal Article | |
dcterms.source.volume | 168 | |
dcterms.source.issn | 0305-0548 | |
dcterms.source.title | Computers and Operations Research | |
dc.date.updated | 2024-10-08T05:03:26Z | |
curtin.department | School of Elec Eng, Comp and Math Sci (EECMS) | |
curtin.accessStatus | Open access | |
curtin.faculty | Faculty of Science and Engineering | |
curtin.contributor.orcid | Bui, Hoa [0000-0002-1698-6383] | |
curtin.contributor.orcid | Loxton, Ryan [0000-0001-9821-2885] | |
curtin.contributor.researcherid | Loxton, Ryan [F-9383-2014] | |
curtin.contributor.scopusauthorid | Bui, Hoa [57201853363] | |
curtin.contributor.scopusauthorid | Loxton, Ryan [24438257500] | |
curtin.repositoryagreement | V3 |