Metaheuristic Solver Architecture¶
Draft 2025 Problem solving Architecture
This article examines the architectural design of metaheuristic solvers. This solver will be sequential and non-distributed. Another article in the future will be devoted to distributed solving.
What is a solver ? A solver seeks to find a solution for a specific problem using algorithms. In other words, it is a function sovler that takes three parameters: an instance of a problem, a set of algorithms and a set of solutions (at the beginning of optimization can be empty).
The metaheuristics are used to solve instances of different problems and in particular NP-hardness problems. They group together many algorithms that can be used separately or in a composition and are subject to Hybridation. Some metaheuristic examples: simulated annealing, iterated local search, genetic algorithm etc. The choice of a metaheuristic or composition is made on expert knowledge and the characteristics of the problem.
The complexity of implementing a metaheuristic-based solver is due to the quantity, genericity, and numerous interactions between objects. Furthermore, to obtain good results, it will always be necessary to calibrate the solver parameters on a subset of problem instances.
Special attention to the implementation of certain parts of the solver is important because runtime performance is a determining factor for efficient solving.
Architecture overview¶
The architecture can be decomposed into five phases: parameterization, solver definition, context, resolution implementation, and data gathering.
Parameterization To be able to tune the algorithms according to the problem to be solved, the solver must take parameters as input. And it is configured the methods according to the parameters before solving the problem to not have an impact on the performance. To build the set of methods, the most appropriate factor and design patterns.
Solver defintion It is the minimal subset to solve a problem, it is the definition of the problem, the solution and the algorithms.
Context The solver needs contextual elements to work. These can be used by algorithms or resolution phase.
Resolution implementation The optimization phase executes the implementation plan, during this phase data is collected either to reparameterize the algorithms or to collect various statistics and collect the results.
Being able to capture a snapshot during the results phase can be valuable in some situations, as it allows you to resume the solving process from the last save point. However, depending on the complexity of the solver, this is not always easy to implement it.
Data gathering It allows you to retrieve results and collect statistics related to the optimization. Due to its use of system input/output, this component represents the slowest part of the solver. Therefore, its implementation must be particularly careful, incorporating features such as buffering and the ability to disable certain data collection.
Fig. 2 Solver architecture¶
Generic/Specialize dilemma¶
Determining a good balance between a generic solver and a specialized solver is not trivial.
The implementation of specialize sovler is more straightforward because the solver is dedicate on the one problem and utilizes a predetermined set of algorithms. The outcome is a reduction of the code complexity beteween interaction objects. Moreover, this permits the optimization of calculations to a very precise extent.
A generetic solver handle many problem especially with a different representation of the solution (exemple a bit or float vector) can be difficle to implement.
Generic types, Cost of adding new features
Generic types¶
La diversité des problèmes résolus par les métaheuristiques, avec des représentations de solutions variées (bits, nombres flottants, etc.), rend l’utilisation de types génériques intéressant.
En C++, l’utilisation des templates impose une organisation spécifique du code, où l’ensemble de l’implémentation est généralement placé dans les fichiers d’en-tête (.h), contrairement à la séparation classique entre déclarations et définitions. Cette contrainte est due au mécanisme d’instanciation des templates, qui nécessite que le compilateur ait accès à la définition complète du template au moment de son utilisation.
Cette organisation des templates implique une recompilation de la bibliothèque à chaque modification du projet. Pour les bibliothèques volumineuses, cela engendre un coût de compilation significatif, pouvant impacter la productivité lors du développement de solveurs spécifiques.
Pour réduire le temps de compilation, l’utilisation d’outils comme ccache, qui met en cache les fichiers intermédiaires, est recommandée.
Deplus, la complexité du code est accure ce qui impact sur l’ajout de future fonctionnalité et donc de la prise en mains du projet.
Cost of adding new features¶
L’impact de la généricité générique
la comphésion des class/struct générique peut-être plus difficile niveau de leur implication et intérations.
En C++, l’analyse des érreurs à la compilsation liée à la templetisation peux être complexie.
Fig. 3 Solver Genericity vs cost¶
Loading solver parameters.¶
L’instance d’un problème.
Les paramtères des algorithmes
Zero code feature flags
Desgin paterne -> Factory
Performance analysis¶
Callgrid
To be discuss¶
Zero cost Abstration