Minimum Size Instance

Because instances of PLP in the same equivalence class share the same set of optimal solutions, once one instance is solved, the solution can be stored in a database and retrieved whenever a solution to an instance of PLP of the same class is necessary [Dowsland 1987a]. The most straightforward way to identify each equivalence class in a database is to encode the set of efficient partitions defining the class. This way, given a new instance, it is possible to compute the set of efficient partitions and compare it with the entries in the database. One possible problem is that the cardinality of this set increases with the number of boxes packed.

Another approach is to select a unique class representative. This way, only four integers are necessary to represent the class, independent of the number of boxes in the optimum packing. One option for defining an equivalence class representative is the instance that minimizes the area ratio, the Minimum Area Ratio Instance (MARI). But the minimization problem can have a solution at an open boundary, or at a non-integral interior point [Dowsland 1984]. In these cases the dimensions of the MARI can only be approximated, when using integers. Different approximations can generate different instances within the same class, complicating the identification process.

Another candidate for equivalence class representative is the Minimum Size Instance (MSI), the instance that minimizes the dimensions of both the pallet and the box. We say is the Minimum Size Instance of a class if for all instances in the same class,

Enter the dimensions of the pallet (X and Y) and dimensions of the box (A and B) and hit the submit button.

Questions? Suggestions? Comments?