This paper considers the problem of optimally placing circles in a rectangular region within an intelligent cutting and packaging system. A mathematical model and analysis of this problem are presented. A Python implementation of the gradient projection method for finding a local minimum in this problem is proposed, taking into account the specific features of the problem. The proposed implementation is compared with methods from the scipy.optimize Python library for constrained nonlinear optimization. It is shown that the authors' proposed implementation is faster.
Like many other spatial optimization problems, circle packing problem is available on the packomania
website[
The article [
Beam search is the main part of the algorithm that implements local search. It is a shortened version of decision tree search. At each level of the tree, only a limited number of the best nodes (beam width) are selected for further branching, and the rest are discarded. The potential of each node is evaluated using a greedy strategy called Minimum Local-Distance Position (MLDP). This strategy consists of sequentially placing each subsequent circle in a position where the distance to already placed circles or to the edges of the strip is minimal. This ensures dense packing at the local level.
The article [
The Tabu Search (TS) procedure is a local search that uses prohibition rules and convergence criteria to prevent search loops. After finding a local optimum, a perturbation operator is used to obtain a new solution, which in turn is optimized again using TS and accepted if it is better than the previous one.
Research in this area continues. For example, the DCPACK (Discretized-Space Circle Packer
Algorithm) algorithm was proposed [
Although the circle packing problem is a nonlinear programming problem with quadratic constraints, the proposed approach transforms it into a sequence of integer linear programming problems, which allows the use of eficient ILP methods to obtain guaranteed lower and upper bounds on the optimal value.
Article [
Since this algorithm is based on a mathematical model with complex nonlinear dependencies, it can be classified as a nonlinear programming method. However, due to the use of “jumps” to find better solutions, bypassing exhaustive search, it can also be classified as a heuristic method.
In [
Another approach is used in [
The last three works use the local optimization algorithm as a sub-task many times in global search. Thus, the search for an efective algorithm for local optimization is relevant.
The goal of this study is to implement a local optimization algorithm in Python based on the gradient projection method and taking into account the specifics of the task at hand. After that, compare the resulting implementation with the built-in optimization algorithms of the scipy.optimize library.
This article is structured as follows: Section 2 contains the problem statement, mathematical model, and its properties. Section 3 presents the algorithmic features of the implemented method. Section 4 provides the results of numerical experiments and their comparison with built-in Python local optimization methods. Section 5 contains conclusions.
The circle packing problem considers an index set of circles with known radii , ∈ = {1, . . . , } and a strip of fixed width and (a priori) unbounded length . The goal is to place the circles inside the smallest rectangle of size × so that no two circles overlap and no circle extends beyond the rectangle’s boundary.
The mathematical model of the problem of packing circles into a strip as a mathematical programming
problem looks like this [
Properties of the mathematical model. 1. The number of variables in the problem is 2 + 1, that is, we have an optimization problem in the space R2+1. 2. The objective function is linear. 3. The number of constraints is = 4 + ( − 1) .
2 4. 4 constraints are linear, and the rest are inversely convex. 5. The optimal solution is located at an extreme point of the feasible region. 6. At the extreme point of the feasible region, 2 + 1 inequalities are active. 7. The upper estimate of the number of local minima is 2+1.
Thus, we have a nonlinear nonconvex conditional optimization problem.
To solve the problem, the gradient projection method (Rosen’s method) is used[
The problem under consideration has two important features. First, all constraints of the problem at any point are concave. This means that despite the nonlinearity of some of the constraints, the specified method of constructing the direction of movement will not immediately take us out of the feasible region. And some constraints will cease to be active during movement. That is why such constraints must be periodically removed from the working list. Second, since the objective function is linear, any step in the direction of descent will decrease the objective function. This means that at each step we will stop only when we “hit” some constraint, which means that at each step a new constraint will become active and be added to the working list.
The pseudocode for the maximum step that does not violate linear constraints is given in Algorithm 2, and the pseudocode for the maximum step that does not violate nonlinear constraints is given in Algorithm 3.
Algorithm 1 Gradient projection method for strip packing
The proposed algorithm was implemented in Python using matrix operations from the NumPy
library[
/ if 0 < < lin then end if 9: end for 10: return lin Algorithm 3 Computation of nl Require: , , , _, Ensure: nl 1: for nonlinear ∈ _ do ← ( − )2 + ( − )2 if < then
continue end if ← 2 ←
2 − 4 if < then
continue
end if
nl ← min{ | ∈ {
13: end for
14: return nl
← ( − )2 + ( − )2 − ([] + [])
5:
6:
7:
and are widely used in publications to compare optimization results[
It was discovered that when the number of circles grows large, the SLSQP method often produces unstable or unrealistic results because it is a local solver that becomes highly sensitive to initialization, scaling, and constraint handling. For small problems it behaves reasonably, but at larger scales the numerical gradients and quadratic models degrade. The solver may converge to infeasible or extreme points unless carefully bounded and restarted from multiple initial positions.
Trust-constr and COBYLA runs slower than SLSQP but sometimes has better resul. However, for 100 circles the run exceeded the 15-minute time limit.
trust-constr
Value
During the preparation of this work, the author(s) used GPT-5 in order to: Grammar and spelling check. After using these tool(s)/service(s), the author(s) reviewed and edited the content as needed and take(s) full responsibility for the publication’s content.