An exact cutting plane method for solving p-dispersion-sum problems
From MaRDI portal
Abstract: This paper aims to answer an open question recently posed in the literature, that is to find a fast exact method for solving the p-dispersion-sum problem (PDSP), a nonconcave quadratic binary maximization problem. We show that, since the Euclidean distance matrix defining the quadratic term in (PDSP) is always conditionally negative definite, the cutting plane method is exact for (PDSP) 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 the (PDSP). The numerical results show that the method outperforms other exact methods for solving (PDSP), and can solve to optimality large instances of up to two thousand variables.
This page was built for publication: An exact cutting plane method for solving p-dispersion-sum problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405713)
