2024-03-29T15:33:38Zhttp://digital.csic.es/dspace-oai/requestoai:digital.csic.es:10261/1648402020-12-13T09:21:26Zcom_10261_60com_10261_4col_10261_439
DIGITAL.CSIC
author
Lizarraga, Evelia
author
Blesa, Maria J.
author
Blum, Christian
funder
Consejo Nacional de Ciencia y Tecnología (México)
funder
Generalitat de Catalunya
funder
European Commission
funder
Ministerio de Economía y Competitividad (España)
2018-05-16T11:19:13Z
2018-05-16T11:19:13Z
2017-04-20
17th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2017; LNCS 10197: 60- 74 (2017)
http://hdl.handle.net/10261/164840
10.1007/978-3-319-55453-2_5
http://dx.doi.org/10.13039/501100002809http://dx.doi.org/10.13039/501100003141http://dx.doi.org/10.13039/501100003329http://dx.doi.org/10.13039/501100000780
Both, Construct, Merge, Solve and Adapt (CMSA) and Large Neighborhood Search (LNS), are hybrid algorithms that are based on iteratively solving sub-instances of the original problem instances, if possible, to optimality. This is done by reducing the search space of the tackled problem instance in algorithm-specific ways which differ from one technique to the other. In this paper we provide first experimental evidence for the intuition that, conditioned by the way in which the search space is reduced, LNS should generally work better than CMSA in the context of problems in which solutions are rather large, and the opposite is the case for problems in which solutions are rather small. The size of a solution is hereby measured by the number of components of which the solution is composed, in comparison to the total number of solution components. Experiments are conducted in the context of the multi-dimensional knapsack problem. © Springer International Publishing AG 2017.
eng
closedAccess
Construct, merge, solve and adapt versus large neighborhood search for solving the multi-dimensional knapsack problem: Which one works better when?
artículo
TGljZW5jaWEgQ1NJQyAKClBhcmEgcXVlIGVsIHJlcG9zaXRvcmlvIERpZ2l0YWwuQ1NJQyBwdWVkYSBhbG1hY2VuYXIgeSBkaXN0cmlidWlyIGVsIG9iamV0byBkaWdpdGFsIGRlcG9zaXRhZG8sIAplcyBuZWNlc2FyaW8gcXVlIGxhIHBlcnNvbmEgcXVlIGhhZ2EgZWwgZGVww7NzaXRvIGxlYSB5IGFjZXB0ZSBsYXMgY29uZGljaW9uZXMgZXN0YWJsZWNpZGFzIGVuIAplc3RhIGxpY2VuY2lhOiAKCkVsL2xvcyBhdXRvci9lcyBvIHBvc2VlZG9yL2VzIGRlbCBjb3B5cmlnaHQgZGVsIHRyYWJham8gZGVwb3NpdGFkbyBvIGVuIHN1IGNhc28gbGEgcGVyc29uYSAKZGVsZWdhZGEgcGFyYSBoYWNlcmxvLCBnYXJhbnRpemEgYWwgQ1NJQyBlbCBkZXJlY2hvIG5vIGV4Y2x1c2l2byBwYXJhIGRpc3RyaWJ1aXIsIGFsbWFjZW5hciB5IApwcmVzZXJ2YXIgZW4gZm9ybWF0byBlbGVjdHLDs25pY28gZWwgb2JqZXRvIGRpZ2l0YWwgZGVwb3NpdGFkby4KCkVsIGRlcG9zaXRhbnRlLCBlbiBjYXNvIGRlIHVuYSBvYnJhIGNvbiBtw6FzIGRlIHVuIGF1dG9yLCBnYXJhbnRpemEgcXVlIGxvIGhhY2UgcmVzcG9uc2FibGVtZW50ZSAKZW4gbm9tYnJlIHkgY29uIGNvbnNlbnRpbWllbnRvIGRlIGxvcyBkZW3DoXMgY29hdXRvcmVzLgoKRGVjbGFyYSBxdWUgc2UgdHJhdGEgZGUgdW4gdHJhYmFqbyBvcmlnaW5hbCB5IG5vIGVzdGEgc3VqZXRvIGEgcmVzdHJpY2Npb25lcyBkZSBjb3B5cmlnaHQgY29uIAp0ZXJjZXJvcyBwYXJhIHBvZGVyIG90b3JnYXIgYWwgQ1NJQyBsb3MgZGVyZWNob3MgcmVxdWVyaWRvcyBlbiBlc3RhIGxpY2VuY2lhLgoKU2kgZWwgdHJhYmFqbyBkZXBvc2l0YWRvIGNvbnRpZW5lIG1hdGVyaWFsIGRlbCBxdWUgZWwgYXV0b3Igbm8gcG9zZWUgZWwgY29weXJpZ2h0LCBlbCBhdXRvciAKZGVjbGFyYSBxdWUgaGEgb2J0ZW5pZG8gZWwgcGVybWlzbyBuZWNlc2FyaW8gZGVsIHByb3BpZXRhcmlvIGRlbCBjb3B5cmlnaHQgcGFyYSBnYXJhbnRpemFyIGFsIApDU0lDIGxvcyBkZXJlY2hvcyBkZXNjcml0b3MgZW4gZXN0YSBsaWNlbmNpYSwgeSBxdWUgZWwgcG9zZWVkb3IgZGVsIGNvcHlyaWdodCBlc3TDoSBjbGFyYW1lbnRlIAppZGVudGlmaWNhZG8geSByZWNvbm9jaWRvIGVuIGVsIHRleHRvIG8gY29udGVuaWRvIGRlbCBhcmNoaXZvIGRlcG9zaXRhZG8uCgpFbCBhdXRvciBhY2VwdGEgcXVlIGVsIENTSUMgcHVlZGUsIHNpbiByZWFsaXphciBjYW1iaW9zIGVuIGVsIGNvbnRlbmlkbywgY29udmVydGlyIGVsIHRyYWJham8gYSAKY3VhbHF1aWVyIG1lZGlvIG8gZm9ybWF0byBjb24gb2JqZXRpdm9zIGRlIHByZXNlcnZhY2nDs24uCgpBc2ltaXNtbyBlbCBhdXRvciBhY2VwdGEgcXVlIGVsIENTSUMgcHVlZGUgY29uc2VydmFyIG3DoXMgZGUgdW5hIGNvcGlhIGRlIGVzdGUgdHJhYmFqbyBwYXJhIGdhcmFudGl6YXIgCmxhIHNlZ3VyaWRhZCB5IGxhIHByZXNlcnZhY2nDs24gZGUgbG9zIGFyY2hpdm9zLgoKRWwgQ1NJQyBwcmVzZXJ2YXLDoSB5IGRpZnVuZGlyw6EgZXN0ZSB0cmFiYWpvLiBFbiBlbCBjYXNvIGRlIHF1ZSBubyBwdWVkYSBjb250aW51YXIgbWFudGVuaWVuZG8gZWwgCmFyY2hpdm8gY29tbyBwYXJ0ZSBkZWwgcmVwb3NpdG9yaW8gaW5zdGl0dWNpb25hbCBzZSByZXNlcnZhIGVsIGRlcmVjaG8gZGUgZGV2b2x2ZXIgZWwgY29udGVuaWRvIGFsIApkZXBvc2l0YW50ZS4gU2kgZXN0byBubyBlcyBwb3NpYmxlIChwb3JxdWUgbGEgY29tdW5pZGFkLCBjb2xlY2Npw7NuIGV0Yy4geWEgbm8gZXhpc3RhIG8gZWwgYXV0b3Igbm8gCmVzdMOpIGxvY2FsaXphYmxlKSwgZWwgbWF0ZXJpYWwgcG9kcsOtYSBzZXIgYXJjaGl2YWRvIGNvbW8gcGFydGUgZGVsIGFyY2hpdm8gZGlnaXRhbCBkZSBsYSBpbnN0aXR1Y2nDs24uIAoKU2kgbGEgY29udHJpYnVjacOzbiBzZSBiYXNhIGVuIHRyYWJham9zIGZpbmFuY2lhZG9zIG8gcGF0cm9jaW5hZG9zIHBvciBvcmdhbml6YWNpb25lcyBkaXN0aW50YXMgYWwgCkNTSUMsIGRlY2xhcmEgaGFiZXIgY3VtcGxpZG8gY29uIGN1YWxxdWllciBkZXJlY2hvIHkgb2JsaWdhY2nDs24gZXhwcmVzYWRvcyBlbiBlbCBjb250cmF0byBvIGFjdWVyZG8gCmNvbiBkaWNoYXMgb3JnYW5pemFjaW9uZXMuIAoKRWwgbm9tYnJlIGRlbCBkZXBvc2l0YW50ZSBxdWVkYXLDoSBjbGFyYW1lbnRlIGlkZW50aWZpY2FkbyBwb3IgZWwgQ1NJQyBjb21vIGVsIGRlbCBhdXRvciBvIHByb3BpZXRhcmlvIApkZSBsYSBjb250cmlidWNpw7NuLCB5IGVsIENTSUMgbm8gcmVhbGl6YXLDoSBuaW5ndW5hIGFsdGVyYWNpw7NuIGRlIHN1IGNvbnRyaWJ1Y2nDs24sIGV4Y2VwdG8gbGFzIHJlZmVyaWRhcyAKYWwgZm9ybWF0bywgcGVybWl0aWRhcyBwb3IgZXN0YSBsaWNlbmNpYS4K
URL
https://digital.csic.es/bitstream/10261/164840/1/accesoRestringido.pdf
File
MD5
42637ae8545636bc41605c1740a9a84e
15753
application/pdf
accesoRestringido.pdf