A cutoff time strategy based on the coupon collector's problem
dc.contributor.author | Lobo, FG | |
dc.contributor.author | Bazargani, M | |
dc.contributor.author | Burke, EK | |
dc.date.accessioned | 2020-05-19T08:26:15Z | |
dc.date.available | 2020-05-19T08:26:15Z | |
dc.date.issued | 2020-01-01 | |
dc.identifier.citation | Lobo, Fernando G. et al. "A Cutoff Time Strategy Based On The Coupon Collector’S Problem". European Journal Of Operational Research, vol 286, no. 1, 2020, pp. 101-114. Elsevier BV, doi:10.1016/j.ejor.2020.03.027. Accessed 19 May 2020. | en_US |
dc.identifier.issn | 0377-2217 | |
dc.identifier.uri | https://qmro.qmul.ac.uk/xmlui/handle/123456789/64179 | |
dc.description.abstract | Throughout the course of an optimization run, the probability of yielding further improvement becomes smaller as the search proceeds, and eventually the search stagnates. Under such a state, letting the algorithm continue to run is a waste of time as there is little hope that subsequent improvement can be made. The ability to detect the stagnation point is therefore of prime importance. If such a point can be detected reliably, then it is possible to make better use of the computing resources, perhaps restarting the algorithm at the stagnation point, either with the same or with a different parameter configuration. This paper proposes a cutoff time strategy. It presents a method that is able to reliably detect the stagnation point for one-point stochastic local search algorithms applied to combinatorial optimization problems. The strategy is derived from the coupon collector's problem, and is scalable based on the employed perturbation operator and its induced neighbourhood size, as well as from feedback from the search. The suitability and scalability of the method is illustrated with the Late Acceptance Hill-Climbing algorithm on a comprehensive set of benchmark instances of three well-known combinatorial optimization problems: the Travelling Salesman Problem, the Quadratic Assignment Problem, and the Permutation Flowshop Scheduling Problem. | en_US |
dc.publisher | Elsevier | en_US |
dc.relation.ispartof | European Journal of Operational Research | |
dc.rights | This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. | |
dc.rights | Attribution 3.0 United States | * |
dc.rights.uri | http://creativecommons.org/licenses/by/3.0/us/ | * |
dc.title | A cutoff time strategy based on the coupon collector's problem | en_US |
dc.type | Article | en_US |
dc.rights.holder | © 2020 The Authors. | |
dc.identifier.doi | 10.1016/j.ejor.2020.03.027 | |
pubs.notes | Not known | en_US |
pubs.publication-status | Published | en_US |
rioxxterms.funder | Default funder | en_US |
rioxxterms.identifier.project | Default project | en_US |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |
This item appears in the following Collection(s)
Except where otherwise noted, this item's license is described as This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.