Packing convex homothetic polytopes into a cuboid

• Datum: 2018
• Hauptverfasser: Stoyan, Yu. G., Chugay, A. M.
• Format: Artikel
• Sprache: English; Ukrainian
• Veröffentlicht: Інститут енергетичних машин і систем ім. А. М. Підгорного Національної академії наук України 2018
• Schlagworte: packing; homothetic polytopes; rotations; optimization; phi-functions; UDC 519.85
• Online Zugang: https://journals.uran.ua/jme/article/view/135431
• Назва журналу: Journal of Mechanical Engineering

This paper deals with the optimization problem of packing a given set of homothetical arbitrarily oriented convex polytopes without their overlapping in a linear parallelepiped of minimal volume. Phi-functions are proposed to be used as a constructive means of the mathematical modeling of a given problem. On the basis of the phi-function a mathematical model of the problem is constructed for two convex non-oriented polytopes, and its main properties which influence the choice of the strategy for solving the problem are examined. The obtained mathematical model presents the problem in the form of a classical problem of nonlinear programming, which makes it possible to use modern solvers for searching for a solution. Effective methods for finding valid starting points and locally optimal solutions based on homothetic transformations are proposed. To search for local extrema of the formulated optimization problems, a special method of decomposition has been developed, which allows us to significantly reduce computational costs due to a considerable reduction in the number of inequalities. The key idea of the optimization procedure allows us to generate subsets of the domain of admissible solutions at each stage of searching for a local extremum. Parallel computations were used to search for local extrema, which made it possible to reduce time expenditures. Numerical examples are given. The methods proposed in the work can be used for solving the problem of packaging convex polytopes.