Optimal placements of flexible objects: Part II: A simulated annealing approach for the bounded case

Abstract

This paper is a continuation of the first part, where we considered regular arrangements of flexible objects for the unbounded case. The present part deals with a simulated annealing algorithm maximizing the number of flexible objects in equilibrium placements within rigid boundaries. The forces caused by the boundary are taken into account, i.e., the bounded case of placements is considered. The simulated annealing procedure makes use of the special structure of the underlying configuration space and relationships between deformations of flexible objects and resulting forces. This allows us to obtain tight bounds for the annealing parameters which result in n 3/2 · ln 5/2 n and n · ln 2 n time bounds, respectively, for the computation of equilibrium states by two different cooling schedules. The deformation/force formula is derived from a physical model of flexible discs and is based on numerical experiments which were performed for different materials and different sizes of objects. The algorithm was first implemented and tested for the unbounded case. The run-time is relatively short, even for large numbers of placed discs. These results are compared to the analytical ones obtained for regular placements in the first part of the paper, and agreement between these two sets of results are observed. Furthermore, several experiments for placements with boundary conditions were carried out and the resulting placements clearly show the effect of the forces from the rigid boundary. The specialized and provably efficient simulated annealing algorithm proposed in this paper is therefore a very effective tool for computing equilibrium states of placements and hence useful for the design of new amorphous polymeric materials and package cushioning systems as mentioned in Part I of this paper. © 1997 IEEE.