EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3049. A quaternion formulation of the volume maximization problem

Invited abstract in session MD-7: Cutting and Packing 4 - 3D irregular, stream Cutting and Packing (ESICUP).

Monday, 14:30-16:00
Room: 1019 (building: 202)

Authors (first author is the speaker)

1. Jonas Tollenaere
NUMA, KU Leuven
2. Tony Wauters
Computer Science, KU Leuven

Abstract

In volume maximization problems, the objective is to extract the largest three-dimensional item(s) with variable scaling from a larger container. To achieve this, values for the continuous translation and rotation variables should be determined so that the items can be maximally scaled up, without violating any containment or non-overlapping constraints. Applications of these problems appear in various real-world contexts, such as gem cutting and circuit manufacturing, where finding better solutions is typically highly valuable. While effective heuristic methods have previously been developed to tackle these problems, the attention to exact methods has been rather limited. One of the reasons for this is most likely the complexity involved with mathematically optimizing rotation in three-dimensional space. Angle-based rotation representations such as Euler angles lead to trigonometric expressions, which are challenging for exact solution methods. Therefore, quaternions are better suited for this purpose. Using quaternions, we can formulate the orientation of an object through quadratic expressions. This allows us to mathematically formulate volume maximization problems with convex containers as quadratically constrained programs, based on quaternions, that can be solved exactly. In this presentation, we will introduce volume maximization problems, give some insights into its applications and heuristic methods, and formulate the aforementioned quadratically constrained models.

Keywords

Status: accepted

Back to the list of papers