RAGE: A novel strategy for solving non-polynomial problems through the random generation of solutions and incremental reduction of the number of candidates: A case study applied to the design of the network infrastructure for connected vehicles

• Published in: Expert systems with applications 2023-03, Vol.213, p.118900, Article 118900
• Main Authors: da Silva, Cristiano Maciel, Sarubbi, João Fernando Machry, Mokhtari, Somayeh, dos Santos, Leonardo Alvarenga Lopes, Silva, Lucas Diniz, de Souza, Fernanda Sumika Hojo, Guidoni, Daniel Ludovico, Nogueira, Jose Marcos Silva
• Format: Article
• Language: English
• Subjects: Computer networks; Infrastructure design; Networks with infrastructure; Novel strategy for solving combinatorial problems; Vehicular networks
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2022.118900

This work presents RAGE, a novel strategy designed for solving combinatorial optimization problems where we intend to select a subset of elements from a very large set of candidates. For solving the combinatorial problem, RAGE generates a customizable number of random solutions, computes the objective function for each solution, and then scores each candidate element in terms of the value returned by the objective function. After that, RAGE removes a customizable number of candidate elements presenting the smallest score when considering all solutions generated. This cycle is called one iteration. The heuristic loops performing iterations until there are left the exact number of candidates that we are looking for. In order to evaluate the efficiency of RAGE, we perform experiments showing how RAGE behaves when we change the number of random solutions generated per round, and the number of candidate elements removed per round. Finally, we apply RAGE for solving an NP-Hard problem related to the allocation of infrastructure for vehicular communication. The results show that RAGE requires 40,000 evaluations of the objective function to achieve the same result found by the baseline using 175,000 evaluations of the objective function, which, in this case study, represents a drastic reduction of the computational overhead in order to reach the same target. •Novel strategy for solving combinatorial problems.•Strategy has the potential to support decisions near real-time systems.•Applicable when we must select a subset of elements from a set.•Linear complexity.