# Optimization Algorithm for Cutting Masonry with a Roboti Saw
## 2 Materials and Methods
In modular masonry, a limited set of cut objects is used, each with several repetitions. It was necessary to add other minimization parameters (number of cuts, size of loss residues) into our model. However, none of the exploited mathematical algorithms brought a reliable and optimal solution in a reasonable amount of time [29; 30; 31]. Therefore, it was decided to develop an algorithm for optimizing the cutting of masonry elements in 1D space, as detailed in the following parts of this article, together with an example of application and comparison with the existing methods. The size of a masonry element \(V\) [mm] is expressed as:  
\[V=L\cdot W\cdot H, \tag{1}\]  
where \(L\) [mm] is the length of the element, \(W\) [mm] is the width of the element and \(H\) [mm] is the height of the element. The size of a masonry element is predetermined and constant, which the algorithm describes as the size of a container. The cut parts of masonry elements have the same height and width as the whole element in question. They only differ in the length of \(a_{1},\ldots,a_{n}\), where \(n\) designates the number of objects. The optimization problem can be converted to a 1D space problem, where the size of the container is taken as its length \(L\), for which the following condition applies:  
\[L\leq\sum_{i\in S_{k}}a_{i}\forall k=1,\ldots,B, \tag{2}\]  
where \(B\) is the number of containers (the entire masonry element) and \(S\) is a subset of objects (cuts). The task is to identify the splitting of a set \(\{1,\ldots,n\}\) into a \(B\) subset \(S_{1}\cup\ldots\cup S_{B}\) for which condition (2) applies. The minimum number of subsets is the optimal solution of the problem:  
\[\text{min}B=OPT, \tag{3}\]Minimizing and constraining conditions for a robotic saw can be formulated as follows:  
* The number of whole masonry elements is minimal: \(B=\sum_{i=1}^{n}y_{i}\), where \(y_{i}=1\) for the containers used. * The condition of the minimal number of cuttings \(T\) can be formulated as minimizing the number of wasted pieces: \(W=\sum_{i=1}^{n}w_{i}\), where \(w_{i}=1\) for containers with unused space. A fully filled container reduces the number of cuts by \(1\). * Other constraints can be formulated as: \[\sum_{j=1}^{n}a_{i}\cdot x_{ij}\leq L\cdot y_{i},\] where \(y_{i}\in\{0,1\},x_{ij}\in\{0,1\},\forall i\in\{1,\ldots,n\},\) and \(\forall j\in\{1,\ldots,n\}\). \[\sum_{i=1}^{n}x_{ij}=1,\] where \(x_{ij}\in\{0,1\},\forall i\in\{1,\ldots,n\},\) and \(\forall j\in\{1,\ldots,n\}\). Object \(j\) is placed in container \(i\) if \(y_{i}=1\) for the used containers and \(x_{ij}=1\)[32]. To optimize the number of cuttings of masonry elements, we must apply certain simplifications to our problem. The minimal possible length of the cuts defines the maximal possible number of objects in container \(N\). This value is limited from above by technological processes of cutting the masonry elements, which significantly reduces the difficulty of finding the optimal solution:  
\[\max N=\left\lceil\frac{L}{\min a_{i}}\right\rceil,\forall i\in\{1,\ldots,n\}, \tag{4}\]  
The technological processes of robotic masonry cutting are considered:  
\[\min a_{i}\geq 50\text{ mm}, \tag{5}\]  
According to their length, cut objects can be classified into smaller groups. The lower and upper limits of the number of containers can be applied as constraints to our problem:  
\[OPT\cdot L\leq\sum_{d=1}^{s}m_{t}\cdot a_{t}\leq n\cdot L, \tag{6}\]  
where \(n\) is the number of objects, \(m_{t}\) is the number of elements in group \(t\), \(a_{t}\) is the size of elements in group \(t\) and \(s\) is the maximum number of groups. The number of groups and elements found in each group is not limited by the algorithm. However, larger numbers of groups negatively affect the calculation time [33]. On the other hand, smaller numbers of groups negatively affect the accuracy of the algorithm.