## 4 Hybrid Packing Strategy Based on Genetic Algorithm--Linear Programming
### Linear Programming  
This study employs coin-or branch and cut (CBC) solvers for the purpose of solving linear programming models and obtaining the optimal solution. A CBC solver uses an improved simplex algorithm to solve the linear programming problem. The simplex algorithm is an iterative method that starts with feasible vertices (i.e., feasible solutions) and moves along the edges of the feasible region until it reaches the optimal vertex. In each iteration, the algorithm selects a variable that can be increased or decreased to improve the objective function, while remaining within the feasible region. The algorithm terminates when the optimal solution conditions are satisfied or when the specified maximum number of iterations is reached. The improved simplex algorithm reduces the number of operations required for each iteration and lowers the computational complexity of each iteration, thereby making it more efficient in practice and able to converge to an optimal solution faster. In addition, the CBC solver uses techniques such as degenerate handling and numerical stability checks to improve the performance and accuracy of the simplex algorithm. After obtaining the packing solution, it is checked to ensure that it meets the requirements of the constraint conditions and objective functions in the mathematical formulation section. Simultaneously, necessary adjustments and modifications are made to the packing solution to meet the requirements of the constraint conditions and objectives, and the final packing solution is obtained. The procedure for improving the solution using linear programming can be outlined as follows:  
Step 1: Initialization of the algorithm. The coordinate sequence of the optimal solution obtained by the genetic algorithm is obtained as the initial workpiece coordinate list. Additionally, the width of raw materials and the maximum time allowed for the algorithm operation are set. Step 2: Generate possible workpiece discharge directions. Traverse each potential direction (e.g., 0\({}^{\circ}\), 90\({}^{\circ}\), 180\({}^{\circ}\), and 270\({}^{\circ}\), represented by integer values 0, 1, 2, and 3) in order to compile a comprehensive list of the potential workpiece orientations. Step 3: Develop a linear programming model. The model is expressed as a collection of constraints and an objective function. Constraints dictate that every workpiece must be contained within the raw material board and must not overlap with any other workpiece. The objective function aims to maximize the utilization of packing materials. The linear programming model is as follows:  
\[\text{maximize }MaxU=\frac{\sum\limits_{i=1}^{n}S_{i}}{L\times H_{\text{ max}}}\times 100\% \tag{10}\]  
\[\text{subject to }\Omega_{i}\in\Omega,\ 1\leq i\leq p \tag{11}\]  
\[0\leq S_{i}\leq\sum\limits_{i=1}^{n}S_{i},\ 1\leq i\leq p \tag{12}\]  
\[\sum\limits_{i=1}^{n}S_{i}\leq L\times H_{\text{max}},\ 1\leq i\leq p \tag{13}\]  
\[\Omega_{i}\cap\Omega_{j}=\varnothing,\ 1\leq i<j\leq p \tag{14}\]  
\[\theta_{i}\in\theta,\ 1\leq i\leq p,\ 0\leq\theta\leq 2\pi \tag{15}\]  
\[L,H_{\text{max}}\in\mathbb{R} \tag{16}\]  
Formula (11) indicates that all workpieces to be arranged must be completely contained within the rectangular sheet. Formula (12) indicates that the area of each workpiece cannot exceed the sum of the areas of all the workpieces, while Formula (13) indicates that the sum of the areas of all the workpieces cannot exceed the product of the plate length and the maximum contour height of the packing result. Formula (14) indicates that the workpieces to be arranged cannot overlap, while Formula (15) indicates that the allowable rotation angle of the workpieces to be arranged must meet the process requirements. Step 4: Utilize the CBC solver to solve the linear programming model. If a feasible solution is identified, meaning a solution that adheres to all constraints, the program will output the optimal packing solution. If a feasible solution is not found, expand the boundaries to explore more search space.