article · 2005
Query Optimization
Yuning Chen, Jin-kao Hao, Yuning Chen, Y. Chen, J. K. Hao
Cited by 0Abstract and details only
Abstract
Abstract The quadratic multiple knapsack problem (QMKP) consists in as-signing objects with both individual and pairwise profits to a set of limited knapsacks in order to maximize the total profit. QMKP is a NP-hard com-binatorial optimization problem with a number of applications. In this pa-per, we present an iterated responsive threshold search (IRTS) approach for solving the QMKP. Based on a combined use of three neighborhoods, the algorithm alternates between a threshold-based exploration phase where so-lution transitions are allowed among those satisfying a responsive threshold and a descent-based improvement phase where only improving solutions are accepted. A dedicated perturbation strategy is utilized to ensure a global di-versification of the search procedure. Extensive experiments performed on a set of 60 benchmark instances in the literature show that the proposed ap-proach competes very favorably with the current state-of-the-art methods for the QMKP. In particular, it discovers 41 improved lower bounds and attains all the best known results for the remaining instances. The key components of IRTS are analyzed to shed light on their impact on the performance of the algorithm.
Cite this paper
Chen, Y., Hao, J.-K., Chen, Y., Chen, Y., & Hao, J. K. (2005). Query Optimization.
Chen, Yuning, et al. “Query Optimization.” 2005.
Chen, Yuning, Jin-kao Hao, Yuning Chen, Y. Chen, and J. K. Hao. 2005. “Query Optimization.”
Chen, Y. et al. (2005) ‘Query Optimization’.
@article{chen2005query,
title = {{Query Optimization}},
author = {Chen, Yuning and Hao, Jin-kao and Chen, Yuning and Chen, Y. and Hao, J. K.},
year = {2005}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.