# Combinatorial Optimization Problems and Metaheuristics: Review, Challenges, Design, and Development
## 2 Materials and Methods
### Optimization Problem  
Human beings face difficulties daily--challenging or contradictory situations--that need to be resolved to reach the desired purpose. These situations, in practical terms, can be called problems. Theoretically, from a psychological perspective, a problem can be summed up as difficulty that triggers an analytical attitude of a subject to acquire knowledge to overcome it [30; 31; 32]. From a computer science perspective, a problem is a task that an algorithm can solve or answer. From a practical perspective, computational problems can be broadly classified into six main categories of problems: ordering, counting, searching, decision, function, and optimization. Concerning ordering, counting, and searching, their own definitions describe their objectives as problems. A decision problem is a class of problems that decides after the analysis of a situation. The return of this type of problem is an answer (a judgment) that only is determined by two possible outputs [\"Yes\", \"No\"] or [1, 0][30; 31]. Whereas a function problem is an extension of the decision, any data type can be returned. An optimization problem (OP) is a class of problems resolved by optimization methods that aim to find an optimal solution in a vast set of possible solutions [2; 33; 34; 35; 33]. Consequently, the output of an optimization problem is the solution itself. **Definition 1**. : _An optimization problem can be formalized in the following way:_  
\[P=(S,\,f,\,\Omega) \tag{1}\]  
_where:_  
* \(P\) _represents the optimization problem;_
* \(S\) _symbolizes the search space of the problem domain;_
* \(f\) _represents the objective function (OF); and_
* \(\Omega\) _corresponds to the set of problem's constraints._  
The _search space_\(S\) is defined through a set of variables \(=\{X_{1},\ X_{2},\ldots,\ X_{n}\}\), generally called _decision variables_ or _design variables_. They can be seen as the data or the dimensions that are explored to search for a _solution_. The _search space_ may be subject to a set of _constraints_\(\Omega\) or restrictions. These restrictions are a set of definitions used to specify whether a _solution_ is feasible or not. In other words, they regulate whether a _solution_ can be accepted according to the rules of the problem domain. The _f fitness function_ or _objective function_ is used to assess and determine the quality of the _solutions_ and guide the search process. **Definition 2**. : _A fitness function has as an output a real number (\(\mathbb{R}\)), often called fitness._  
\[f:S\ \rightarrow\mathbb{R} \tag{2}\]  
\[\forall\,s\in S,\,f(s)=fitness\ (\mathbb{R})\]  
This number enables the possibility to compare the performance of all possible solutions of a certain _optimization problem_[6; 23; 34; 36]. Optimization problems are divided into two categories of problems, (1) continuous and (2) combinatorial problems [35]. Continuous optimization problems are composed of continuous decision variables, and they can generate an infinite number of valid solutions. Combinatorial optimization problems (COP)--also known as discrete optimization problems--are defined by discrete decision variables and their elements. The solution of a COP is represented by an arrangement of these elements. Since a solution is a combination (or permutation) of elements, a COP has a finite number of solutions. The definition of the encoding rules between combinations or permutations will depend on the needs of the problem and its solution representation. **Example 1**. : _Considering Travel Salesman Problem (TSP), a solution is a route formed by an ordered arrangement of cities. In other words, the order of the cities is essential, and their repetition is not allowed. Therefore, this solution's encoding must follow the permutation rules where the elements cannot be repeated._  
Continuous optimization can use derivatives and gradients to describe the slope of a function [35]. However, combinatorial optimization does not count with this support.