Skip to content

STATEMENT_ENG.md

Latest commit

 

History

History
32 lines (23 loc) · 2.73 KB

STATEMENT_ENG.md

File metadata and controls

32 lines (23 loc) · 2.73 KB
Raw

The Non-Local Student Problem

Statement

Vacation is over, and you must leave your hometown for the big city to continue your studies. However, there is a minor detail: apparently, all your belongings (tiliches) will not fit in your "San Juan" egg carton box. Furthermore, the cardboard cannot support too much weight. Is there a way to pack your things, or will you have to leave your rooster, "Peso Pluma," behind in his cage?

Your egg box measures $L$ in length, $W$ in width, and $H$ in height, with a maximum weight capacity of $K$ kilograms. You want to pack $N$ objects, each shaped like a small box with dimensions $l_i$ (length), $w_i$ (width), $h_i$ (height), and a weight of $k_i$ kilograms. Your sole objective is to pack as many objects as possible—regardless of whether they are food, clothes, or your tiger print blanket—and you do not care if they get crushed by weight or sudden movements during your return trip.

Keep in mind that your egg box follows the laws of classical physics: no two objects can occupy the same space, partially or entirely, nor can any object be left floating. Additionally, since you have OCD, you require all objects to be aligned parallel to the main box (no free rotations allowed).

Mathematical Formulation

  • The objective is to maximize the number of objects (small boxes) that can be packed. Let $P$ be a packing configuration (which objects, their positions, and orientations) and $\mathbf{1}P$ be the indicator function that determines whether an object is packed. The optimization function is as follows, where $B$ is the set of packable objects: $$ \max_P \sum{b \in B} \mathbf{1}_P(b) $$

  • Weight Capacity Constraint: The sum of the weights of the packed objects must not exceed the maximum capacity $K$. This is expressed as follows, where $k$ is the function representing the weight of an object $b$: $$ \sum_{b \in B} \mathbf{1}_P(b) \cdot k(b) \le K $$

  • Containment Constraint: All objects must be contained within the box dimensions. Therefore, for each object $b_i$ at position $(x_i, y_i, z_i)$, the following must be verified: $$ l_i+x_i \le L$$ $$ w_i+y_i \le W$$ $$ h_i+z_i \le H$$

  • Overlap Constraint: The volumes of any two objects must not intersect. Treating the objects as sets, for any two distinct objects $b_i$ and $b_j$, it must hold that $b_i \cap b_j = R$, where $R$ is either the empty set $\emptyset$ or a flat region in space.

  • Stability Constraint: Every object must have support on its bottom face, either by being in contact with the top faces of other objects or directly touching the floor of the box.

Methodological References

  • 3D Single Container Loading Problem with Weight and Static Stability Constraints
  • 3D Bin Knapsack Packing Problem
  • Separating Axis Theorem