The focus of this research is the creation of intelligent geometric design technologies. The system employs state-of-the-art methods and tools to automate the arrangement and enhance the placement of 3D shapes. Specifically, the aim is to resolve practical issues in optimizing additive manufacturing processes. This is accomplished by merging artificial intelligence techniques with novel computational solutions for superior results. The article presents a nonlinear optimization approach for solving 3D irregular packing problems with arbitrarily moved and rotated objects. Phi-functions and quasi-Phifunctions are used to describe interactions between the 3D objects. The following formulation presents the packing problem in mathematical terms, along with an analysis of its features. A local optimization algorithm is introduced to identify solutions, with a focus on the characteristics that have been delineated. The results of computational experiments suggest that the proposed solution method is effective for 3D irregular packing optimization.
This paper proposes the development of intelligent geometric design technologies that leverage advanced methodologies and tools to automate and optimize the placement of geometric objects in space. These technologies address applied challenges in optimizing additive manufacturing by integrating artificial intelligence (AI) and innovative computational approaches to achieve optimal solutions.
Three-dimensional packing problems are a useful model for studying well-established optimization scenarios frequently encountered in various engineering disciplines. There is considerable current momentum towards discovering efficient strategies for tackling these problems. These problems find relevance across various real-world scenarios, including the efficient placement of geometric objects, defined by their shape, within constrained spaces. Frequently, the resolution of a 3D packing challenge entails determining the placement of all provided objects within containers of minimal size.
Packing dilemmas constitute essential elements of mathematical and computational modelling. These problems are inherently challenging due to their intricate interplay with optimization, geometric configuration, and space utilization. These challenges catalyze innovation in the field, particularly in algorithms and computational methodologies. These innovations are vital for providing solutions to sophisticated real-world problems in the domains of engineering and science. The advancement and refinement of methodologies for addressing these problems are paramount to the continuous development of natural and information-based systems.
Packing problems are prevalent across many scientific and engineering fields. Often, real-world tests are substituted with computer-based modelling, which greatly minimizes time, physical materials, and overall expenses. Take, for instance, reference [1]; this work explores the most effective ways of arranging objects, which can be turned any which way inside a space that has limits. This study highlights noteworthy enhancements in the effectiveness of packing and the smart use of available resources. Progress in the field has been accelerated by improvements in information technology, specifically when studying particles that vary in size (as is seen in [2]). Reference [3] presents a technique that relies on reinforcement learning; it's used to pack odd 3D shapes into a storage area. This method considers physics and the turning of the shapes to assist. A key feature of this technique is lessening the requirements for learning via the creation of likely moves that aid in training. To elaborate, [4] presents a solver based on learning, focusing on packing objects of any shape.
Applications are numerous and span various domains, including biology, geology, medicine, nanotechnology, robotics, and pattern recognition. These implementations also benefit control systems, vehicle construction, chemistry, power and mechanical engineering, and shipbuilding.
The inherent complexity of packing problems, classified as NP-complete, has spurred the exploration of approximation methods. These methods frequently exhibit a heuristic character. The repertoire includes sophisticated search rules [3,4], the principles of genetic algorithms [5], algorithms inspired by ant and bee behaviors, and simulated annealing [6]. Mathematical programming methods [7,8] and their hybrid or integrated variants [9] constitute further solution approaches.
According to reference [4], the progression of a standard solution algorithm is typically characterized by three repeating phases. The initial phase involves the selection of an order for the objects. The subsequent phase entails the positioning of the objects based on the selected order. The final phase concerns the computation of the objective function's value. It should be noted, however, that the positioning of these objects is subject to several variations, primarily distinguished by the following elements: the trajectory the objects take, the rotation constraints applied, and whether the process tolerates or actively prevents overlap.
Many publications impose restrictions on the rotation of three-dimensional objects, limiting them to specific angles, such as 45 or 90 degrees, or completely prohibiting alterations to an object's orientation. For instance, reference [11] utilizes elementary translational movement to arrange convex polytopes. Lamas-Fernandez et al. (2023) have also developed voxel-based approaches to address the 3D irregular packing problem [13]. The research in [12] introduces the HAPE3D algorithm, which focuses on packing polyhedra with rotations limited to eight predetermined angles around the coordinate axes. Finally, the study documented in [14] concludes that determining object orientations across a full 360-degree range in 3D is not a practical solution.
In the face of the daunting task of developing meaningful mathematical models, formulating equivalent expressions for continuous rotations of three-dimensional geometric figures is a pursuit by a select few researchers. In this context, techniques for ellipsoid packing are examined, leveraging both continuous and differentiable nonlinear optimization strategies, as demonstrated in [15, 16]. Packaging multiple convex 3D objects is the primary subject of discussion in reference [17].
This research is devoted to developing an intelligent system that will optimize the 3D printing process of many industrial parts using unique intellectual tools and technologies for modelling and solving optimization problems of geometric design. The proposed approach involves modelling and solving the optimization problem of packing non-convex geometric objects.
To this end, a multifaceted approach is employed, integrating mathematical and computer simulation methodologies. These methodologies are meticulously designed to accurately capture the interactions (non-intersection conditions) between geometric objects. This strategy enables formulating the primary problem as a nonlinear optimization problem. The mathematical underpinnings of our methodology are rooted in the phi-functions method, exhaustively delineated in [17]. This method provides a rigorous analytical representation of both the constraints that prevent intersection and the constraints that ensure the location of objects in the container. A critical aspect of our methodology is the incorporation of continuous rotational transformations and parallel translational motions of objects, ensuring a comprehensive and precise representation of the geometric constraints.
The primary goal of this research is to develop an intelligent geometric design system that enhances the automation and optimization of 3d shape arrangement, particularly for additive manufacturing (3d printing) applications. The work seeks to improve packing efficiency by integrating artificial intelligence (AI) with advanced computational geometry techniques.
This research advances the field of intelligent geometric design by introducing a novel optimization framework for 3d irregular packing. Combining AI techniques with computational geometry provides a viable additive manufacturing solution, demonstrating theoretical innovation and industrial applicability. The computational experiments confirm the method’s effectiveness, paving the way for smarter, more efficient manufacturing processes. 2. Problem definition The proposed intellectual system is predicated on a distinctive universal mathematical model of optimization geometric design, constructed with specialized intellectual means of modelling this category of problems. These intellectual means encompass specific functions designated as "phifunctions" [18]. These functions facilitate the construction of a generalized universal mathematical model in the form of a nonlinear optimization problem.
Let there be the following convex geometric objects: a convex polyhedron J 1 given by vertices p1t=( p11t , p12t , p13t ) , t ∈ T 1={1,2 , ... , ϱ1 }; . a circular cylinder J 2={ X ∈ ℝ3 , x2+ y2− R22 ≤ 0,0 ≤ z ≤ H 2 }; a sphere J 3={ X ∈ ℝ3 , x2+ y2+ z2− R3 ≤ 0 };
2 a circular cone J 4={ X ∈ ℝ3 , x2+ y2−c24 ( z− E4 )2 ≤ 0 , z ≥ 0 , E4 >0 }; a truncated circular cone J 5={ X ∈ ℝ3 , x2+ y2−c52( z− E5 )2 ≤ 0 , E5 ≥ H 5 ≥ 0 , 0 ≤ z ≤ H 5 }; a spherical segment J 6={ X ∈ ℝ3 , x2+ y2+( z + H 6 )2− R62 ≤ 0 , z− H 6 ≤ 0,0< H 6< R6 }; a half-space J 7={ X ∈ ℝ3 , z ≤ 0 }.
We suppose that each concave geometric objects Qi , i∈ I ={1,2 , ... , n }, is a finite union of κi convex geometric objects Oi=∑ Oik where Oik are geometric objects of kind J r , r =1,2 , ... ,7 .
k=1 The location of each object Oik with respect to the local coordinate system of Oi is given with placement parameters uik=( vik , θik ) , k ∈ K i={1,2 , ... , κi } .
A container C can be a rectangular parallelepiped ℂ1={X ∈ ℝ3 , w1 ≤ x ≤ w2 , l1 ≤ x ≤ l2 , η1 ≤ x ≤ η2}, where w1 ≥ 0 , l1 ≥ 0 , η1 ≥ 0 ,or a right circular (rectangular prism or cuboid) cylinder ℂ2 with height ℂ3={ X ∈ ℝ3 , x2+ y2+ z2− R2 ≤ 0.
Basic problem. Pack geometric objects O j , i∈ I , without their mutual overlapping in the container C so that its volume will reach the minimum value.
We assume h=h2−h1 (h2 ≥ h1) and radius r , or a solid sphere
Geometric objects Oi (in what follows objects) both are allowed to be translated by a vector vi=( xi , yi , zi ) and to rotate by angles θi=( φi , ψi , ωi ) . ui=( vi , θi )=( xi , yi , zi , φi , ψi , ωi ) gives a location of Oi in 3 u=( u1 , u2 , ... , un )∈ ℝ6 n gives the location of all Oi , i∈ I , in ℝ .
Hence, a
vector 3 ℝ . Thus, the vector
Then, components of the vector ( u ,ℏ )=( u1 , u2 , ... , un ,ℏ )∈ ℝ6 n+m , where m can be either 1 or 3 or 6, form a complete set of variables. In addition, an object Oi translated by a vector vi and rotated through angles θi is designated by Oi ( ui ) and a container ℂ with variable size ℏ is denoted as ℂ (ℏ ) .
On the ground of phi-functions [17,18] and quasi-phi-functions [19,20], a mathematical formulation of the problem can be stated as follows: where ( u¿ ,ℏ ¿ , Z¿ )=argmin H (ℏ ) s . t .( u ,ℏ , Z )∈ Λ⊂ ℝN Λ={( u ,ℏ , Z )∈ ℝN : Φij ( ui , u j , ℤij )≥ 0 , i < j∈ I ,
Φi ( ui ,ℏ )≥ 0 , i∈ I , L(ℏ )≥ 0 } H (ℏ )={ (w2−w1¿)(l2−l1)(η2−η1) if ℂ=ℂ1 , (h2−h1) r2 if ℂ=ℂ2 ,
r3 if ℂ=ℂ3 ,
L(ℏ )={
w1 ≥ 0 , l1 ≥ 0 , η1 ≥ 0 , w2−w1 ≥ 0 , l2−l1 ≥ 0 , η2−η1 ≥ 0 if ℂ=ℂ1 ,
h2−h1 ≥ 0 , h1 ≥ 0 , r ≥ 0 if ℂ=ℂ2 ,
r ≥ 0 if ℂ=ℂ3 ,
(
Here, the inequality Φij ( ui , u j , ℤij )≥ 0 ensures non-overlapping Oi and O j while the inequality Φi ( ui ,ℏ )≥ 0 guarantees a containment of Oi within ℂ (ℏ ) i.e. Φi ( ui ,ℏ ) is a phi-function for Oi and B (ℏ )=ℝ3 \int ℂ (ℏ ) where int ℂ (ℏ ) is the interior of ℂ. A vector ℤij can consist of at most q components.
Let us examine the fundamental properties of the mathematical model.
ϵi ϵ j
Since Oi=∪s=1 Ois and O j= ∪p=1 O jp, then Oi ∩ O j=⌀ if Ois ∩ O jp=⌀ , s∈ K i , p∈ K j . Consequently Φij ( ui , u j , ℤij )=min {Φisjp ( ui , u j , ℤisjp ) , s∈ K i , p∈ K j } where Φisjp ( ui , u j , ℤisjp ) is either a Φ-function or a quasi-phi-function for Ois and O jp . Thus, Φij ( ui , u j ℤij )≥ 0 if min {Φisjp ( ui , u j , ℤisjp ) , s∈ K i , p∈ K j }≥ 0.
Each quasi Φ-function Φisjp ( ui , u j , ℤisjp ) in general, is a function of the kind Φisjp ( ui , u j , ℤisjp )=max {Ψ isjpa( ui , u j , ℤisjp ) , a∈ Aisjp=Bisjp∪ ℂisjp={1,2 , ... , aisjp+1 , aisjp+2 , ... , ϰisjp }}. Thus, Φisjp ( ui , u j , ℤisjp )≥ 0 if no fewer than one of the inequality systems {Ψ isjpa( ui , u j , ℤisjp )≥ 0 , a∈ Aisjp , holds true. It is evident Φij ( ui , u j , ℤij )≥ 0 if at least one of the inequality systems {Ψ isjpa( ui , u j , ℤisjp )≥ 0 , s∈ K i , p∈ K j , where a∈ Aisjp is satisfied. So, the κi κ j number of systems is ςij=∏ ∏ ϰisjp .For the sake of convenience, we rename the inequality s=1 p=1 systems as
{Ψ itj ( ui , u j , ℤitj )≥ 0 , t ∈ T ij={1,2 , ... , ςij }.
It follows from the previous items that Φij ( ui , u j , ℤij )≥ 0 , i < j∈ I , if at least one of the inequality systems {Ψ itj ( ui , u j , ℤitj )≥ 0 , i < j∈ I , where t ∈ T ij , holds true. For the sake of convenience, we rename the inequality systems as
Gτ ( u , ℤ )≥ 0 , τ ∈ Υ ={1,2 , ... , ϑ }
n n where ϑ =∏ ∏ ςij .
i=1 j
Each function of the family Ψ isjpa( ui , u j , ℤisjp ) , a∈ ℂisjp contains an additional vector ℤisjp consisting in general of several components. This means that each inequality system contains at κi κi most ∏ ∏ κi κ j variables.
i=1 j=1 Each function Φi (ui ,ℏ )is presented as
Φi ( ui ,ℏ )=min {Φis ( ui ,ℏ ) , s∈ K i={1,2 , ... , κi }} where Φis ( ui ,ℏ ) is the Φ-function for Ois and C (ℏ )= R3 \int ℂ (ℏ ).
Based on items 3 and 4 we draw a very important conclusion: the feasible region Λ can be presented as follows:
ϑ Λ=∪τ=1 Λτ, where Λτ is specified by the inequality system
F τ ( u ,ℏ , ℤτ )={Φi ( ui ,ℏ )≥ 0 , i∈ I ,={f τ 2( ξτ 2 )≥ 0 ,
Gτ ( u , ℤτ )≥ 0 , f τ 1( ξτ 1 )≥ 0 ,
L(ℏ )≥ 0 , ...................
f τ ϵ ( ξτ ϵ )≥ 0 κi κi n where ξτ t consists of components of vectors u and ℤτ , ϵ >∏ ∏ κi κ j+n ∏ κi. i=1 j=1 i=1 Note that the functions f τ j ( ξτ j ) , j=1,2 , ... , ϵ , are smooth with respect to their variables.
Consequently, solving the problem (
( u¿ τ ,ℏ ¿ τ )=argmin H (ℏ ) s . t .( u ,ℏ )∈ Λτ⊂ ℝN , τ ∈ Υ .
This means we have a theoretical chance to compute a global minimum solution of the problem
(
Since the solution space of the stated problem is defined by many inequalities, we propose solving
the problem (
Let us consider the stages in detail. 5. Constructing feasible starting points 5.1. Covering geometric objects with spheres In order to cover objects Oi with spheres Si={ X ∈ ℝ3 , x2+ y2+ z2−ri2 ≤ 0 } of minimum radii ri , with placement parameters vi=( xi , yi , zi ). i∈ I , we solve the following problems: ri0=min ri s . t .( ri , vi )∈ Di⊂ ℝ4 , i∈ I ,
Di={( ri0 , vi0 )∈ ℝ4 , Φi ( ri , vi )≥ 0 }.
Here, Φi ( ri , vi )≥ 0 provides non-overlapping Oi and a set
ℂi={ X ∈ ℝ3 ,−( x− xi )2−( y − yi )2−( z− zi )2+ri2 ≥ 0}.
As a result of solving the problem, a point ( ri0 , vi0 ) is calculated. In what follows, we remove the origins of the incoordinate systems of Oi so that they coincide with the centers of spheres Si , i∈ I . This means that a translation vector of Oi in ℝ3 is a vector vi=( xi , yi , zi ) which coincides with the centre coordinates of the sphere ℂ .
i
After that, we solve a packing problem of spheres Si , i∈ I , into a sphere ℂ3 of minimum
volume if n ≤ 30. The problem is solved just as presented in [18]. Consequently, a point ( v¿ , R¿ )
close to a global minimum point is identified. Randomly given rotation angles φi=φi0 , ψi=ψi0and
ω =ωi0 of Oi , i∈ I , we form a starting point ( u0 , θ0 )=( v¿ , φ0 , ψ0 , ω0 )∈ Λ for the problem (
V ij = Fij (ℏ ⋄ )=min Fij (ℏ ) s . t .( ui , u j ,ℏ )∈ Ωij⊂ ℝ18 , i < j∈ I ,
C
(
Fij (ℏ )=( wi2j−wi1j )( li2j−li1j )( ηi2j−ηi1j ) , Ωij={( ui , u j ,ℏ )∈ ℝ18 : Φij ( ui , u j )≥ 0 , Φi ( ui ,ℏ )≥ 0 , Φ j ( u j ,ℏ )≥ 0 , Lij (ℏ )≥ 0 },
Lij (ℏ )=( wi1j ≥ 0 , li1j ≥ 0 , ηi1j ≥ 0 , wi2j−wi1j ≥ 0 , li2j−li1j ≥ 0 , ηi2j−ηi1j ≥ 0 ) .
The inequality Φij ( ui , u j )≥ 0 insures int Oi ∩ int O j=⌀ while Φi ( ui ,ℏ )≥ 0 guarantees a placement of Oi within Qij.
Consequently, a local minimum point ( ui¿ , u¿j ,ℏ ¿ ) close to a global minimum for the problem
(
After that, we pack in pairs Oi , i∈ I , into spheres Sij of the minimum radius Ri¿j , i < j∈ K ={1,2 , ... , k }, i.e. we solve the following problems:
V S= 34 π min {Ri3j , i < j∈ I }s . t . (ui , u j , Rij)∈ Ωij⊂ ℝ13 , where
Ωij={( ui , u j , Rij )∈ ℝ16 : Φij ( ui , u j )≥ 0 , Φi ( ui , Rij )≥ 0 , Φ j ( u j , Rij )≥ 0 , Rij ≥ 0 }.
The inequality Φij ( ui , u j )≥ 0 provides int Oi ∩ int O j=⌀ while Φi ( ui ,ℏ )≥ 0 insures arrangement of Oi within Sij.
Let point ( ui* , u* , Ri*j ) be an approximate point to a global minimum point of the problem.
j
To derive a starting point belonging to Ωij, we introduce homothetic coefficients hi of objects Oi and O j and assume that the coefficients are variable. Thus, we have the opportunity to enlarge or diminish sizes of objects Oi and O j changing their homothetic coefficients. Consequently, the phifunction for Oi ( ui , hi ) and O j ( u j , h j ) depends on hi and h j , i.e. the -function takes the form Φij ( ui , u j , hi , h j ) , and the -function for Oi ( ui , hi ) and cl ( ℝ3 \ ℂij ) where ℂij is either Qij or Sij , depends on hi , i.e. the -function has the kind Φi ( ui ,ℏ , hi ) . Since for any 0<hi< ∞ , objects Oi ( ui , hi ) are homothetic, then Φij ( ui , u j , hi , h j ) and Φi ( ui , hi ,ℏ ) have the same form for any 0<hi< ∞ . The homothetic coefficients hi , i∈ T , form a vector h=( hi , h j )∈ ℝ2 . Furthermore, we select such sizes ℏ ' of container ℂij (ℏ ' ) which guarantees placement of objects Oi and O j into ℂij (ℏ ' ) and fixℏ ' . It permits to formulation the helper problem
g g ∑ hi¿=max ∑ hi s . t . (u , h)∈ Δ⊂ ℝ14 , i=1 i=1 where Δ={( u , h )∈ ℝ14 , Φij ( ui , u j , hi , h j )≥ 0 , Φk ( uk , hk )≥ 0 ,
hk ≥ 0 , hk−1 ≥ 0 , k =i , j }.
A starting point (u'i , u'j , h' )for the problem is formed in the following manner. We set h'k=0.01, k =i , j , and randomly assign u' so that ν'k∈ Cij (ℏ ' ) , k =i , j . Note that due to h'k=0.01 , k ∈ i , j , we generally have the point (u'i , u'j , h' )∈ Δ.
It is evident if h¿k=1 , k =i , j , then ( ui* , u*j ¿ , h* ) is a global maximum point of the problem (
Now taking the point ( u'i , u'j , h' ) as a starting one, we tackle the problem (
6.1. Packing geometric objects without rotations The stage involves packing objects under fixed rotation angles.
Firstly, we fix the values of the rotation angles φi=φi0 , ψi=ψi0 and ωi=ωi0 , i∈ I . This means
that only translations of objects Oi , i∈ I are allowed. In this case, the problem (
H (ℏ ¿ )=min H (ℏ ) s . t . X ∈ Θ⊂ ℝD Θ={ X =( v ,ℏ , Z )∈ RD : Φij ( vi , v j , Zij )≥ 0,0<i < j∈ I ,
Φi ( vi ,ℏ )≥ 0 , i∈ I , L(ℏ )≥ 0 }, D ≥ 3 n+m .
For computing a local minimum point ( v0* ,ℏ 0* , Z0* ) of the problem, the same solution scheme
is applied to solving the problem (
Computing a local minimum point ( v ,ℏ * , ℤ ) of the problem (
H (ℏ (κ+1)* )=min H (ℏ ) s . t . X ∈ Λκ , ϰ=0,1,2 , .. ..
(
* κ * , Zϰ )∈ Λ a subregion Λκ containing the point ( u ,ℏ κ *
* , Zϰ ) is singled out. A starting point is ( u0* ,ℏ 0* , Z*0 )=( u0 ,ℏ 0 , Z00 ) . A vector ℤ¿ϰ is constructed specially.
The computational process proceeds until H (ℏ (κ+1)* )= H (ℏ κ * ) is fulfilled. This indicates that κ * the point ( u ,ℏ κ *
*
, Zϰ ) is a local minimum point of the problem (
κ * Since ( u ,ℏ κ *
* , Zϰ ) being a local minimum point of the problem H (ℏ κ * )=min H (ℏ ) s.t.
X ∈ Λκ is not in generally a local minimum point of the problem (
* , Zϰ ) . We single out inequality subsystems Ψ ij ( ui , u j , ℤisjpa )≥ 0 , i∈ E1κ , j∈ E2κ , s∈ K i κ , p∈ K j κ , a=aisjp , where spA t sp ij is from the index set
Aisjp, which contain the active inequalities. Note that Ψ ij ( ui , u j , ℤisjpa )=0 , i∈ E1κ , j∈ E2κ , s∈ K i κ , p∈ K j κ .
spa κ κ
Next, we single out inequalities Φisjp ( ui , u j , ℤij )≥ 0 from the inequality system (
Fκ ( u ,ℏ , ℤϰ )≥ 0 for the inequality
subsystems 0 ij . Furthermore, a new vector ℤ¿ϰ which includes new i∈ E10κ , j∈ E20κ , q∈ K i κ , r∈ K 0j κ , q=qsp components of the set ℤisjpq , q∈ Bisjpϰ∪ Cisjpϰ , is formed. It is evident that ( u ,ℏ κ * κ *
* , Zϰ )∈ Θκ+1 .
Thus, if at least one k spq ij >0, then we obtain a new inequality system Fκ+1( u ,ℏ , ℤκ+1 )≥ 0 ¿ specifying a set Λκ+1 ≠ Λκ and a new starting point ¿ where a new vector Zκ includes components spt κ * ℤij , t ∈ Bisjpϰ∪ Cisjpϰ . It follows from the construction that a starting point ( u ,ℏ κ *
* , Zκ ) provides Ψ ij ( ui , u j , Zisjpq )≥ 0 , qrq H (ℏ (κ+1)* )≤ H (ℏ ϰ* ). 6.4. Computing a local minimum point on a feasible subregion computation of local minimum point ( u¿ ,ℏ ¿ , ℤ ) of the problem
¿
Since inequality system Fκ ( u ,ℏ , ℤ )≥ 0 consists in general of a huge number of inequalities, the
Ϝ(ℏ (κ+1)*)=minϜ(ℏ )s.t.(u,ℏ ,ℤ)∈ Λκ,
(
Let a point (uκ*,ℏ κ*,Z*κ)∈ Λκ and some δ>0. Making use of spheres Si with radii ri0, i∈ I , we select Ψisjpt(ui,uj,ℤisjpt)≥0, i∈ A1tκ, j∈ At2κ, s∈ Ki, p∈ K j, t=tisjp, from an inequality system Fκ(v,ℏ ,ℤϰ)≥0 for which the inequalities ‖viκ*−vκ*‖−(ri0+r0j)≤δ ,i∈ A1tκ, j∈ At2κ, ij hold true.
Let ℂ=ℂ1. In this case, we single out the inequalities Φifk(ui,ℏ )≥0, i∈ Ifκ, s∈ Ki, l f ∈ Υ={1,2,..,6}, where Φik(ui,ℏ ) is a -function for an object Ois and f-th half space, for which the inequalities w1−xiκ*−ri0≤ δ2 ,i∈ I1κ,xiκ*+ri0−w2≤ 2 ,i∈ I2κ,
δ l1−yiκ*−ri0≤ δ2 ,i∈ I3κ, yiκ*+ri0−l2≤ 2 ,i∈ I4κ,
δ η1−ziκ*−ri0≤ δ2 ,i∈ I5κ,ziκ*+ri0−η2≤ 2 ,i∈ I6κ δ are fulfilled.
Next, we cover convex objects Oik with spheres ℂik of minimum radii ρik and centers vik=(xik, yik,zik),i∈ I , k∈ Ki. We suppose that the origins of the local coordinate systems of Oik coincide with the centers ℂik,i∈ I , k∈ Ki. Then, the coordinates of centers of circles ℂik with respect to the global coordinate systems of vik(ui)=(xik(ui), yik(ui),zik(ui))=RiT(vik+vi), i∈ I ,k∈ Ki .
Now let us choose inequalities Ψisjpt(ui,uj,ℤisjpt)≥0, i∈ A10κt⊂ A1tκ, j∈ A20κt⊂ At2κ, s∈ Ki⊂ Ki, p∈ K j⊂ K j, and Φik(ui,ℏ )≥0, i∈ Ifκ, s∈ Kϰfi⊂ Ki, f ∈ Υ , for which the t t f Oi are inequalities ‖vis(uiκ*)−vjp(uiκ*)‖−(ρis+ρjp)≤δ ,i∈ A10κt, j∈ A20κt,s∈ Kit, p∈ Ktj,
δ δ 2 w1−xik(uiκ*)−ri0≤ 2 ,,i∈ I1κ,k∈ K1ϰi,xi(uiκ*)+ri0−w2≤ 2 ,i∈ I2κ,k∈ Kϰi, l1−yi(uiκ*)−ri0≤ δ2 ,,i∈ I3κ,k∈ K3ϰi, yi(uiκ*)+ri0−l2≤ 2 ,i∈ I4κ,k∈ Kϰi, δ 4 η1−xi(uiк*)−ri0≤ δ2 ,i∈ I5κ,k∈ K5ϰi,xi(uiκ*)+ri0−η2≤ 2 ,i∈ I6κ,k∈ K6ϰi, δ are satisfied respectively.
Taking inequalities Ψisjpt(ui,uj,Zij)≥0, i∈ A10κt, j∈ A20κt,s∈ Kit, p∈ Ktj, Φifk(ui,ℏ )≥0, i∈ Ifκ, s∈ Kϰfi⊂ Ki, f ∈ Υ , and L(ℏ )≥0, we form the inequality subsystem Fκt(u,ℏ ,ℤϰ)={‖vis(uiκ*)−vst(ui)‖≤ δ ,i∈ A10κt,s∈ Kif
L(ℏ )≥0, 2
δ ‖vis(uiκt)к∗−vjp(ui)‖≤ , j∈ A20κt, p∈ Kif ,
2 Φik(ui,ℏ )≥0,i∈ Ifκ,s∈ Kϰfi⊂ Ki,f ∈ Υ ,
f Ψisjpt(vi,vj,Zij)≥0,i∈ A10κt, j∈ A20κt,s∈ Kit, p∈ Ktj, ={fi2κt(ξi2)≥0 .
fi1κt(ξi )≥0
1 .................. fiqκt(ξi )≥0 q which describes a subregion Λκt such that Xκ∈ (uκ*,ℏ κ*,Z*κ)∈ Λκt⊂ Λκ.
Consequently, searching for a local minimum point of the problem (
The problems are solved until Ϝ (ℏ κ(t+1))= Ϝ (ℏ κ t ) is met, and the point ( uκ * ,ℏ κ * , ℤ*κ ) is
taken as a local minimum point of the problem (
We can diminish the problem dimension for each t . Considering a starting point ( uκ l ,ℏ κ l , ℤκ l ) for the problem Ϝ (ℏ κ (t+1))=minϜ (ℏ ) s.t. ( v ,ℏ )∈ Λκ t, we fix ℤκ t (i.e., appropriate components of Zϰt do not vary). This means that Γ κ t ( u ,ℏ )= Fκ t ( u ,ℏ , ℤκ t ) and z specifies the feasible subregion Λκ t whose dimension is less than that of Λκ t. It evident that ( uκ t ,ℏ κ t )∈ Δκz t and all points of Δκz l ensure non-overlapping objects Oi , i∈ I . Thus, we solve a sequence of problems
H (ℏ κ (t+1))=minH (ℏ ) s . t .( u ,ℏ )∈ Δκz t , t =1,2 , ... ,
until
H (ℏ κ(t+1))= H (ℏ κ t ) is met. Obviously, the point ( uκ(t+1) ,ℏ κ(t+1) , ℤκ t ) is not generally a local
minimum point of the problem (
Taking the point ( uκ(t+1) ,ℏ κ(t+1) , ℤκ t ) as a starting one, we continue to solve the problems (
Open-source ecosystem: IPOPT offers seamless interoperability with platforms like Julia, Python, and MATLAB, which enables antidifferentiation capabilities alongside facilitating higherlevel modelling approaches.
IPOPT's forte lies in the domain of solving large, sparse NLPs. This is primarily attributable to its advanced interior-point framework, efficient sparse linear algebra integration, and adaptability in addressing many problem types. Furthermore, its open-source foundation and ease of use with modern tools make IPOPT indispensable for chemical engineering, economics, and applications in real-time control systems. Optimized outcomes are achieved by pairing it with high-performance linear solvers, such as HSL MA57, and extensions like IPOPT to facilitate effective sensitivity analysis.
The algorithm was tested on various benchmark instances from [14], with the results summarized below.
For packing 36 objects (Fig. 1a): the HAPE3D approach yielded a volume of 12.4 and a runtime of 963 seconds, while our method attained a volume of 10.7 and a runtime of 750 seconds.
For the case of packing 40 objects (Fig. 1b): the HAPE3D approach achieved a volume of 61.9 and a runtime of 999 seconds, while our method achieved a volume of 56.0 and a runtime of 533 seconds. The results of this study are illustrated in Figure 1.
a b
As demonstrated in Figure 2, the intelligent system developed for this study successfully packed 300 non-convex polyhedra. This result demonstrates the system's capacity to address highdimensional problems while effectively maintaining adequate time performance.
The effectiveness of the proposed approach is confirmed by comparing the results of packing non-convex polyhedra with the results presented by the paper's authors [14]. The results of this comparison are shown in Figure 3.
The results demonstrate that the proposed Intelligent Geometric Modeling Framework significantly reduces computation time and enhances the performance metrics across the test cases.
This article outlines a process for developing an intelligent system focused on geometric design. The proposed systems will leverage cutting-edge methods and tools to automate and improve how geometric shapes are arranged within a three-dimensional environment. The core benefit of these technologies will be their ability to find the best possible solutions when applied to practical challenges in additive manufacturing. Artificial intelligence and other novel techniques will be central to achieving optimal results with these systems.
This research introduces a novel method for precisely modelling the three-dimensional irregular packing problem. Employing the phi-function method, we can leverage contemporary nonlinear optimization techniques to address this challenge, including creating initial configurations and determining local minima.
The clustering technique facilitates starting point generation by solving the packing problem involving half the quantity of convex objects characterized by simpler shapes. This strategic simplification notably diminishes the computational requirements of establishing the initial configurations.
The procedure's computational performance is improved by employing a two-step strategy to locate the local optimum. Initially, a linear problem is addressed. A nonlinear problem then succeeds this in the subsequent stage. The displayed results clearly demonstrate the efficacy of this method in finding solutions for the particular irregular packing problem being studied.
This approach significantly improves the accuracy and efficiency of solving 3D packing issues, which has vital implications for the progress of both natural and information systems. This combination exemplifies a strong synergy between mathematical modelling and advanced computational tools. The approach enhances the precision and efficiency of 3D packing solutions, essential for advancing natural and information systems. This integration demonstrates the powerful collaboration between mathematical models and computational techniques.
During the preparation of this work, the authors used Grammarly in order to: Grammar and spelling check. After using this tool, the authors reviewed and edited the content as needed and take full responsibility for the publication’s content.