# Combinatorial Optimization Problems and Metaheuristics: Review, Challenges, Design, and Development
## 4 Results: Standardization, Methodology, and Framework for COP and Metaheuristics
### Problem Representation: Formulation and Standards
#### 4.2.1 Problem Template (PT) Definitions  
**Definition 4**. : _In practical terms, since the problem template defines the higher-level building blocks, it can be defined in the following way:_  
\[P=(O,S,E,\Omega|\phi|A)\ \rightarrow\{p_{1},\ p_{2},\ldots,\ p_{n},\ldots\} \tag{4}\]  
_where:_  
* \(P\) _represents the problem template and if it is followed, it may originate an infinite number of problem instances_ \(\{p_{1},\ p_{2},\ldots,\ p_{n},\ldots\}\)_;_
* \(O\) _corresponds to a nonempty set of objectives_ \(O=\{o_{1},\ o_{2},\ \ldots,\ o_{n}\}\)_;_
* \(S\) _is the search space design or decision variables design_ \(S=\{s_{1},\ s_{2},\ \ldots,\ s_{n}\}\)_;_
* \(E\) _defines a nonempty set of solution encoding rules_ \(E=\{e_{1},\ e_{2},\ \ldots,\ e_{n}\}\)_;_
* \(\Omega\) _(optional) represents set of constraint design_ \(\Omega=\{\omega_{1},\ \omega_{2},\ \ldots,\ \omega_{n}\}\)_;_
* \(\phi\) _(optional) is the admissibility function; and_
* \(A\) _(optional) represents a set of additional algorithms_ \(A=\{\alpha_{1},\ \alpha_{2},\ \ldots,\ \alpha_{n}\}\) _that can be used by instances of_ \(P\)_._  
**Definition 5**. : _Any objective \(\mathsf{o_{i}}\) of \(\mathsf{O}=\{\mathsf{o_{1},\ \mathsf{o_{2},\ \ldots,\ \mathsf{o_{n}}}}\}\) defines the objective direction and has function to determine the quality of a solution, and it can be expressed by:_  
\[\mathsf{O}=\{\mathsf{o_{1},\ \mathsf{o_{2},\ \ldots,\ \mathsf{o_{n}}}}\}\,\ \forall\ \mathsf{o}\in\mathsf{O},\ \mathsf{o}=(\mu,F)\ \ \rightarrow\ \mathbb{R} \tag{5}\]  
_where:_  
* \(\mu\) _represents the objective direction (minimization or maximization); and_
* \(F\) _corresponds to a set of the objective functions for an objective._  
A PT was envisioned to enable the possibility of a problem to have multiple objective functions. The idea is to provide the possibility of a PT to deal with more than one solution's encoding. It is vital to enable other classes of metaheuristics--based on a different encoding--that can also manipulate this problem. Therefore, potentially, it can make the problem resolvable by any metaheuristics without any code changes from both sides. The challenge will be to make these encodings equivalent. It also demands additional objective function and admissibility function. **Definition 6**. : _F corresponds to a set of the pairs defined by the objective function and the solution's encoding it is linked to; therefore, \(F\) can be defined as:_  
\[\text{F}=\{(\text{f}_{1},\varepsilon_{1}),\ (\text{f}_{2},\varepsilon_{2}) \ldots,\ (\text{f}_{n},\varepsilon_{n})\} \tag{6}\]  
\(S\) represents the search space design (SSD), and it is a conceptual view of the search space. From a practical perspective, it shapes the decision variables' scheme by specifying their roles in the search and data types. As a result, it specifies how problem instances must supply the concrete decision variables to work properly and designed by the problem template. **Definition 7**. : _Therefore, a decision variable design is synthesized as:_  
\[S=\{s_{1},\ s_{2},\ \ldots,\ s_{n}\},\ \forall\ s\in S,\ s=(r,d) \tag{7}\]  
_where:_  
* \(r\) _represents the decision variable role in search; and_
* \(d\) _corresponds to the data type of the decision variable (the terminology for_ \(d\) _is defined by the framework)._  
**Remark 4**. : _The SSD is not merely a convention. These specifications must be followed by the objective function, actual decision variables, etc. They are interconnected, and the \"roles\" link them and guarantee that they will perform adequately in a standard way._  
The solution encoding rules E is a set of higher-level definitions used to form a solution instance (representation) for a determined class of problems. This definition is the basis of the \"solution factory\" provided by the framework. In summary, it is a state machine that receives a solution encoding as input and can produce random solutions. **Definition 8**.