Solving Euclidean Max-Sum problems exactly with cutting planes
Citation
Source Title
ISSN
Faculty
School
Funding and Sponsorship
Collection
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.
Related items
Showing items related by title, author, creator and subject.
-
Chong, Yen N. (2001)General routing problems deal with transporting some commodities and/or travelling along the axes of a given network in some optimal manner. In the modern world such problems arise in several contexts such as distribution ...
-
Kulanoot, Araya (2000)The Knapsack Problems are among the simplest integer programs which are NP-hard. Problems in this class are typically concerned with selecting from a set of given items, each with a specified weight and value, a subset ...
-
Radiy, Mamon (2010)The vehicle routing problem (VRP) is to service a number of customers with a fleet of vehicles. The VRP is an important problem in the fields of transportation, distribution and logistics. Typically the VRP deals with the ...