# A Petri Net-Based Algorithm for Solving the One-Dimensional Cutting Stock Problem
## 5 Filtered Beam Search Algorithm Implementation  
Consider the reachability tree construction of the PN-CSP with initial marking \(\mathbf{M}_{0}=[L\ \ \ d_{1}\ \ \ d_{2}\ \ \ \cdots\ \ \ d_{m+1}\ \ \ 0\ \ 0\ \ 0\ \ 0]^{T}\) for a given instance of the 1D-CSP. Starting from this initial marking, all potential solutions are derived by investigating firing sequences leading to the final marking \(\mathbf{M}_{f}=[L\ \ \ 0\ \ 0\ \ \cdots\ \ 0\ \ 0\ \ \omega\ \ \
u\ \ \eta]^{T}\). However, exhaustive exploration of all sequences is computationally intensive. To solve this issue, we use the FBS, which reduces explored markings as we progress in the reachability tree. FBS does not perform backtracking like traditional any-time search methods, optimizing computational efficiency. The effectiveness of FBS depends on parameters \(\alpha\) and \(\beta\), chosen to balance exploration and exploitation. Algorithm 1 outlines our FBS implementation, starting by generating all child nodes from firing transitions \(t_{1},t_{2},\ldots,t_{m}\) at the initial marking or the root node (level 0 or \(L0\)), resulting in \(m\) markings at level 1 (\(L1\)), as shown in Figure 6. In our FBS, each marking at L1 is neither locally nor globally evaluated, treating each node as a potential beam node, contrary to [55]. We made this decision because, by the local evaluation, the algorithm will tend to select the solutions with the largest items placed first, minimizing waste in the initial stock. Preliminary experiments showed this approach yields better solutions compared to selecting only \(\beta\) nodes at \(L1\). Thus, starting from L2, we apply both local and global evaluations, setting \(\alpha\leq\beta\) to ensure solution diversity. ```
1:Number of different item types (\(m\)), stock length (\(L\)), item lengths (\(l_{1},l_{2},\ldots,l_{m}\)), and item orders (\(d_{1},d_{2},\ldots,d_{m}\)). 2:\(F_{best}\)
3:With the instance data, generate the incidence matrices \(\mathbf{I}^{+}\), \(\mathbf{I}^{-}\) and obtain the incidence matrix \(\mathbf{I}\). 4:Generate the initial marking as \(\mathbf{M}_{0}=[L\quad d_{1}\quad d_{2}\quad\cdots\quad d_{m+1}\quad 0\quad 0 \quad 0\quad 0]\). 5:Set the beamwidth \(\beta\) and the filterwidth \(\alpha\). 6:\(F_{best}\leftarrow\infty\)
7:\(W_{w}\gets 0\)
8:\(W_{sw}\gets 0\)
9:Generate level \(L0\) of the reachability tree with the marking \(\mathbf{M}_{0}\) as the root node such that \(Current\ level=\{\mathbf{M}_{0}\}\). 10:\(level\gets 0\)
11:\(Best\ solution\gets False\)
12:whileBest solution is False do
13:for each marking in \(Current\ level\)do
14: Get \(W_{w}\), \(W_{sw}\) and \(F_{global}\). 15:endfor
16:if level \(>1\)then
17: Kept the \(\mu=\min(\beta,|Current\ level|)\) best markings in \(Current\ level\) with the lowest \(F_{global}\) cost and form the set \(\mathcal{B}\) with these markings. Eliminate the remaining markings from \(Current\ level\). 18:else
19: Kept the \(\mu=|Current\ level|\) markings in \(Current\ level\) and form the set \(\mathcal{B}\) with these markings. 20:endif
21:\(New\ level=\emptyset\)
22:for each marking \(\mathbf{M}\) in \(\mathcal{B}\)do
23: Determine the reachable markings \(\mathbf{M}^{\prime}\) from \(\mathbf{M}\) with Equation (6) and form the set \(\mathcal{M}_{r}\) with those reachable markings, where \(r=1,2,\ldots,|\mathcal{B}|\). 24:if\(\mathcal{M}_{r}\
eq\emptyset\)then
25: Obtain \(W_{w}\), \(W_{sw}\), \(F_{local}\) and \(F_{global}\) for each \(\mathbf{M}^{\prime}\in\mathcal{M}_{r}\). 26:if level \(>\)0 then
27: Check whether any marking \(\mathbf{M}^{\prime}\in\mathcal{M}_{r}\) has already been generated previously. If it has, let \(\mathbf{M}^{\prime}_{prev}\in\mathcal{M}_{1}\cup\mathcal{M}_{2}\cup\cdots\cup \mathcal{M}_{r-1}\) be the previously generated marking that is equal to \(\mathbf{M}^{\prime}\in\mathcal{M}_{r}\), and then eliminate from the reachability tree the one with the maximum \(F_{global}\) cost.