# 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.2 Problem Instance (PI) Definitions  
As a complementary part, a problem instance provides the concrete elements that fulfill a problem template's definitions. Therefore, a PI must follow the PI definition to work properly. The framework is not designed to create a hierarchy of COP. Thus, a new problem template is not a subclass of a problem template superclass. The framework was envisioned to have only one problem class that is fed by PT and PI specifications. This feature is supported by a helper class named \"problem decorator\" that instantiates the problem by interpreting these definitions. **Definition 11**. : _Therefore, a problem instance is defined as follows:_  
\[\forall\;p\in P,\;p=(P,\;\overline{S},\;\overline{\Omega},|B)\;\rightarrow\{x _{1},\;x_{2},\;\ldots,\;x_{n}\} \tag{11}\]  
_based on \(P=(O,S,E,\Omega|\phi|A)\rightarrow\{p_{1},\;p_{2},\;\ldots,\;p_{n}\}\)_  
_where:_  
* \(p\) _is a problem instance that follows a_ \(P\) _problem template), and it may originate a finite number of solutions_ \(\{x_{1},\;x_{2},\;\ldots,\;x_{n}\}\)_;_\(P\) is the problem template definition followed by the problem instance (therefore, the problem instance is self-contained unit of software);
* \(\overline{S}\) represents the concrete search space (data) that is composed of decision variable instances \(\overline{S}=\{\overline{s}_{1},\,\overline{s}_{2},\,\ldots,\,\overline{s}_{n}\}\);
* \(R\) defines the roles by linking which decision variable;
* \(\overline{\Omega}\), corresponds to the actual values of the constraint \(\overline{\Omega}=\{\overline{\omega}_{1},\,\overline{\omega}_{2},\,\ldots,\, \overline{\omega}_{n}\}\) and it is only relevant for the instance of the problem; and
* \(B\) is a list of additional algorithms \(B=\{\beta_{1},\,\,\beta_{2},\,\,\ldots,\,\beta_{n}\}\) that can be provided by an instance of the problem. **Definition 12**. : _Therefore, a decision variable instance is defined as follows:_  
\[\overline{S}=\{\overline{s}_{1},\,\overline{s}_{2},\,\ldots,\,\overline{s}_{ n}\},\forall\,\overline{s}\in\overline{S},\,\overline{s}=\left(r,\overline{d}\right) \tag{12}\]  
_where:_  
* \(r\) _represents the decision variable role in search; and_
* \(\overline{d}\) _corresponds to the data of the decision variable._  
The search space template \(S=\{s_{1},\,\,s_{2},\,\ldots,\,s_{n}\}\) defines how the search space instance must be provided \(\overline{S}=\{\overline{s}_{1},\,\overline{s}_{2},\,\ldots,\,\overline{s}_{n}\}\). In other words, each decision variable design \(s=(r,d)\) requests a variable instance \(\overline{s}=\left(r,\overline{d}\right)\) when a problem is built (PI). **Definition 13**. : _A constraint value is defined by:_  
\[\overline{\Omega}=\{\overline{\omega}_{1},\,\,\overline{\omega}_{2},\,\, \ldots,\,\overline{\omega}_{n}\},\,\,\forall\,\overline{\omega}\in\overline{ \Omega},\,\,\overline{\omega}=\left(c,v\right) \tag{13}\]  
_where:_  
* \(c\) _defines the variable (or concept) subjected to a constraint; and_
* \(v\) _defines the constraint value._  
The constraint's design \(\Omega=\{\omega_{1},\,\,\omega_{2},\,\ldots,\,\omega_{n}\}\) defines how the constraint values must be provided \(\overline{\Omega}=\{\overline{\omega}_{1},\,\,\overline{\omega}_{2},\,\, \ldots,\,\overline{\omega}_{n}\}\). Unless otherwise stated, each constraint design \(\omega=\left(c,w,\,\,t\right)\) requires a constraint value \(\overline{\omega}=\left(c,v\right)\) when the problem is created (PI). The B, a set of additional algorithms \(B=\{\beta_{1},\,\,\beta_{2},\,\ldots,\,\beta_{n}\}\), enables the possibility to add \"pieces of software\" in a problem instance. The mechanism is similar to the set A provided in the problem template. However, it is only applicable to the instance and cannot be reused by other instances. If the additional algorithm needs to be shared by other instances, it needs to be added in A. It is conceived to make a problem instance flexible permitting the addition of problem heuristics. **Definition 14**.