# 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
: _A solution encoding is defined by:_  
\[\forall\ \varepsilon\in\text{E},\ \varepsilon=(\mathcal{S},\mathcal{T}, \mathcal{X}|B)\ \ \rightarrow\ \ \{x_{1},\ x_{2},\ \ldots,\ x_{n}\} \tag{8}\]  
_where:_  
* \(\varepsilon\) _describes a solution encoding definition and it may originate a finite number of solutions_ \(\{x_{1},\ x_{2},\ \ldots,\ x_{n}\}\)_;_
* \(\mathcal{S}\) _defines the shape of the solution representation (model's format or data structure);_
* \(\mathcal{T}\) _represents the syntax type used as basis to form;_
* \(\mathcal{X}\) _defines the syntax (rules) form a valid solution; and_
* \(B\) _symbolizes the additional software that can be added to a problem instance._  
The framework must define the syntax types, and it must be designed as an extensible list of classes of syntaxes that are supported by the framework. Therefore, it enables the evolution of the framework capacities according to future needs. Moreover, each syntax type is defined by a particular syntax (rules) that embraces all the points necessary to guide the construction of the solutions, such as tokens (elements), and how they can be arranged (analogous to lexical and grammatical levels of a computer language). Again, these solution syntaxes definitions must be supported by the framework. Furthermore, the framework also needs to provide test tools to certify that a solution representation is well designed, and facilitate this definition. It also may consider a COP design tool to create a level of abstraction to guide and support this process. \(\Omega\), the constraint's design, and \(\phi\), the admissibility function, are optional. Therefore, a problem must be operational without them. Their presence will depend on the characteristics and needs of the problem. \(\Omega\) and \(\phi\) are only in a problem template definition ifit is a constrained optimization problem and it also requires an admissibility function to determine if a problem is feasible or not. **Definition 9**. : _A constraint design is defined by:_  
\[\Omega=\{\omega_{1},\;\omega_{2},\;\ldots,\;\omega_{n}\},\forall\;\omega\in\; \Omega,\;\omega=(c,w,\;t) \tag{9}\]  
_where:_  
* _c defines the variable (or concept) subjected to a constraint;_
* _w defines the comparison operator to apply the constraint rule; and_
* _t defines the constraint data type._  
**Remark 6**. : _Generally, an admissibility function can evaluate all constraints. Thus, in our analysis, it is not necessary to implement one admissibility function per constraint. If it is necessary by a problem not perceived in our review, the constraint design also could consider an admissibility function._  
The A, set of additional algorithms \(\mathrm{A}=\{\alpha_{1},\;\alpha_{2},\;\ldots,\;\alpha_{n}\}\), opens the possibility of adding \"pieces of software\" to the problems, generally using a heuristic of the problem or guessing some aspects of search space characteristics. Therefore, it is a way to add problem knowledge to COP in a standard way. For example, it can provide alternative \"initialization subordinated heuristics\" that can attempt to apply a problem-specific heuristic to initialize the metaheuristics taking advantage of this assumption. **Definition 10**. : _The additional algorithm \(\alpha\) is expressed by:_  
\[\mathrm{A}=\{\alpha_{1},\;\alpha_{2},\;\ldots,\;\alpha_{n}\},\;\forall\;\alpha \in A\;,\;\alpha=(a,g) \tag{10}\]  
_where:_  
* _a corresponds to the additional algorithm itself; and_
* _g indicates the class of the algorithm (group)._  
**Remark 6**. : _The class of the algorithm must be defined by the framework terminology to classify the stand-alone algorithms (self-contained pieces) of the framework according to their class. For example: \"subordinated heuristic initialization\", \"build solution function\", \"subordinated heuristic for selection\", etc._