# Combinatorial Optimization Problems and Metaheuristics: Review, Challenges, Design, and Development
## 1 Introduction  
Combinatorial optimization problems (COPs), especially real-world COPs, are challenging because they are difficult to formulate and are generally hard to solve [1, 2, 3]. Additionally, choosing the proper \"solver algorithm\" and defining its best configuration is also a difficult task due to the existence of several solvers characterized by different parametrizations. Metaheuristics are widely recognized as powerful solvers for COPs, even for hard optimization problems [4, 5, 6, 7, 8]. In some situations, they are the only feasible approach due to the dimensionality of the search space that characterizes the COP at hand. Metaheuristics (MH) are general heuristics that work at a meta-level, and they can be applied in a wide variety of optimization problems. They are problem-agnostic techniques [4, 9, 10, 11, 12, 13] that establish an iterative search process to find an optimal solution for a given problem [6, 14, 15]. Metaheuristics are extensively used in several areas such as finance, production management, production, healthcare, financial, telecommunication, and computing applications that are NP-hard in nature [2, 10, 16]. Nevertheless, a determined metaheuristic cannot have a great performance in all categories of optimization problems because its approach may not work well in several other problems, a hypothesis already proved by \"No Free Lunch\" theorems [14, 15, 17, 18, 19]. These points have \"engaged\" the research community to develop a vast number of metaheuristics [6, 15, 19]. Theoretically, metaheuristics are not tied to a specific problem, thus allowing the same heuristic to be used to solve different types of COPs. Metaheuristics can be adapted to incorporate problem-specific knowledge [4]. However, in practical terms, these incorporations always require some level of customization to adapt them to the peculiarities of a COP. For instance, it is not plug-and-play as occurs with Scikit Learn, where any data and parameters are passed as input for the classifiers. Consequently, this customization requires a set of efforts to effectively ensure that the metaheuristics can properly manipulate the COP solutions' representation, such as methodsfor exploration and exploitation compatible with the solutions' encoding. Moreover, the COP formulation also needs to provide features (data and behaviors) required by metaheuristics to guarantee the proper functioning of the search process for finding an optimal solution. The lack of rules and formalisms to standardize the formulation of COPs and a software design pattern to develop metaheuristics makes this activity more challenging and makes it difficult the progress and consolidation of the field. The absence of standardization and the lack of guidelines to organize COP and metaheuristics [5; 7; 9; 12; 17; 18] make difficult the classification and comparison of metaheuristics' behaviors and performance. Consequently, this leads researchers to start \"almost\" from scratch [3; 5; 9; 16; 18] by building their own version of the algorithm. Consequently, this situation decreases the potential of COP (as a \"piece of software\") and metaheuristic reuse. Especially because they were not designed as independent software units, the interoperability among COPs and metaheuristics without code changes is, most of the time, impossible. Because of this, extra efforts are needed to develop or adjust the metaheuristics to deal with the specific problem [3; 4; 7; 20], reducing the time spent on the analysis and tuning the results. This study aims to provide a thorough review of the COP and MH by presenting the main concepts, algorithms, and challenges. Using these review inputs as a basis, this research proposes a standardization and a framework for COP and MH, named ToGO (Towards Global Optimal). Therefore, this is a review paper accompanied by a framework proposal to provide answers to open questions and well-known issues raised by the research community. From these perspectives, to guide this research, we formulated five research questions.