Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

A Random-Key Optimizer for Combinatorial Optimization

Created by
  • Haebom

Author

Antonio A. Chaves, Mauricio G.C. Resende, Martin J.A. Schuetz, J. Kyle Brubaker, Helmut G. Katzgraber, Edilson F. de Arruda, Ricardo M.A. Silva

Outline

This paper presents the Random Key Optimization (RKO), a versatile and efficient probabilistic local search method for combinatorial optimization problems. RKO uses the concept of random keys to encode solutions into random key vectors and decode them into feasible solutions via a problem-specific decoder. The RKO framework can combine various classical metaheuristic techniques, each operating independently or in parallel, and sharing solutions through an elite solution pool. This modular approach allows the application of various metaheuristic techniques, including simulated annealing, iterative local search, and greedy random adaptive search procedures. The efficiency of the RKO framework, implemented in C++ and publicly available (GitHub repository: github.com/RKO-solver), is demonstrated by applying it to three NP-hard combinatorial optimization problems: the alpha-neighborhood p-median problem, the hub-location tree problem, and the node-capacity-constrained graph partitioning problem. The results demonstrate the framework's ability to generate high-quality solutions across a wide range of problem domains, highlighting its potential as a powerful tool for combinatorial optimization.

Takeaways, Limitations

Takeaways:
We present a flexible and efficient random key-based optimization framework applicable to various combinatorial optimization problems.
Performance enhancement through modular integration of various metaheuristic techniques.
Ensuring reproducibility and scalability through open source code provision
Performance verification through experimental results on various NP-hard problems
Limitations:
Need to design a decoder for a specific problem
Further research is needed on combining metaheuristic techniques and tuning parameters.
Performance evaluation is needed for a wider range of problem types and large-scale problems.
👍