A Random-Key optimizer for combinatorial optimization

Antonio A. Chaves (), Mauricio G. C. Resende (), Martin J. A. Schuetz (), J. Kyle Brubaker (), Helmut G. Katzgraber (), Edilson F. Arruda () and Ricardo M. A. Silva ()
Additional contact information
Antonio A. Chaves: Federal University of São Paulo
Mauricio G. C. Resende: Federal University of São Paulo
Martin J. A. Schuetz: Amazon Advanced Solutions Lab
J. Kyle Brubaker: Amazon Advanced Solutions Lab
Helmut G. Katzgraber: Amazon Advanced Solutions Lab
Edilson F. Arruda: University of Southampton
Ricardo M. A. Silva: Center of Informatics - Federal University of Pernambuco

Journal of Heuristics, 2025, vol. 31, issue 4, No 1, 47 pages

Abstract: Abstract This paper introduces the Random-Key Optimizer (RKO), a versatile and efficient stochastic local search method tailored to combinatorial optimization problems. Using the random-key concept, RKO encodes solutions as vectors of random keys that are subsequently decoded into feasible solutions via problem-specific decoders. The RKO framework is able to combine a plethora of classic metaheuristics, each capable of operating independently or in parallel, with solution sharing facilitated through an elite solution pool. This modular approach allows for the adaptation of various metaheuristics, including simulated annealing, iterated local search, and greedy randomized adaptive search procedures, among others. The efficacy of the RKO framework, implemented in C++ and publicly available, is demonstrated through its application to three NP-hard combinatorial optimization problems: the $$\alpha $$ α -neighborhood p-median problem, the tree of hubs location problem, and the node-capacitated graph partitioning problem. The results highlight the framework’s ability to produce high-quality solutions across diverse problem domains, underscoring its potential as a robust tool for combinatorial optimization.

Keywords: Random-Key Optimizer; Combinatorial Optimization; Metaheuristics; NP-hard problems; C++ Implementation; Parallel Computing (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-025-09568-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:31:y:2025:i:4:d:10.1007_s10732-025-09568-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-025-09568-z

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().