Solving the pallet loading problem

This paper presents new bounds, heuristics, and an exact algorithm for the Pallet Loading Problem (PLP). PLP maximizes the number of boxes placed on a rectangular pallet. All boxes have identical rectangular dimensions and, when placed, must be located completely within the pallet. Boxes may be rotated 90° so long as they are placed with edges parallel to the pallet’s edges. The set of all PLP instances with an area ratio (pallet area divided by box area) less than 101 boxes can be represented by 3,080,730 equivalent classes. Our G5-heuristic finds optimal solutions to 3,073,724 of these 3,080,730 classes and in the remaining 7006 classes only differs from the best known bound by one box. We develop three other heuristics that solve another 54 instances. Finally, we solve the 6952 remaining classes with our exact HVZ algorithm. Only a subset of these classes has been solved previously.     

Analysis of upper bounds for the Pallet Loading Problem

This paper is concerned with upper bounds for the well-known Pallet Loading Problem (PLP), which is the problem of packing identical boxes into a rectangular pallet so as to maximize the number of boxes fitted. After giving a comprehensive review of the known upper bounds in the literature, we conduct a detailed analysis to determine which bounds dominate which others. The result is a ranking of the bounds in a partial order. It turns out that two of the bounds dominate all others: a bound due to Nelissen and a bound obtained from the linear programming relaxation of a set packing formulation. Experiments show that the latter is almost always optimal and can be computed quickly.     

A fast algorithm for identifying minimum size instances of the equivalence classes of the Pallet Loading Problem

In this paper, a novel and fast algorithm for identifying the Minimum Size Instance (MSI) of the equivalence class of the Pallet Loading Problem (PLP) is presented. The new algorithm is based on the fact that the PLP instances of the same equivalence class have the property that the aspect ratios of their items belong to an open interval of real numbers. This interval characterises the PLP equivalence classes and is referred to as the Equivalence Ratio Interval (ERI) by authors of this paper. The time complexity of the new algorithm is two polynomial orders lower than that of the best known algorithm. The authors of this paper also suggest that the concept of MSI and its identifying algorithm can be used to transform the non-integer PLP into its equivalent integer MSI.     

基于对角转轮样式的托盘装箱优化模型

针对托盘装箱问题(PLP),建立了对角转轮样式下具有托盘柔性的整数规划模型,设计了求解模型的启发式算法,并利用VB程序对模型的最优解及装箱图谱进行了讨论分析,结果表明:对角转轮样式就提高具有较大长、宽比箱子的装载效率以及解决装箱压缝问题方面具有明显的优势;而柔性也是影响托盘装载效率的重要因素之一,具有较大的回报率.     

The G4-Heuristic for the Pallet Loading Problem

A new heuristic for the well-known (two-dimensional orthogonal) pallet loading problem (PLP) is proposed in this paper. This heuristic, referred to as G4-heuristic, is based on the definition of the so-called G4-structure of packing patterns. The G4-structure is a generalization of the common used block structure of packing patterns which requires the same orientation of packed boxes within each block. The G4-heuristic yields in approximately 99% of the test instances an optimal solution and solves all instances exactly where at most 50 boxes are contained in an optimal packing. Although the algorithm is pseudo-polynomial the computational experiments reported show that also instances with more than 200 packed boxes in an optimal solution can be handled with a small amount of computational time. Moreover, so far there is not known any instance where the gap between optimal value and the value obtained by the G4-heuristic is larger than one box.     

An <Emphasis Type="Italic">L</Emphasis>-approach for packing (<Emphasis Type="Italic">ℓ</Emphasis>, <Emphasis Type="Italic">w</Emphasis>)-rectangles into rectangular and <Emphasis Type="Italic">L</Emphasis>-shaped pieces

This paper presents an approach using a recursive algorithm for packing (?, w)-rectangles into larger rectangular and L-shaped pieces. Such a problem has actual applications for non-guillotine cutting and pallet/container loading. Our motivation for developing the L-approach is based on the fact that it can solve difficult pallet loading instances. Indeed, it is able to solve all testing problems (more than 20 000 representatives of infinite equivalence classes of the literature), including the 18 hard instances unresolved by other heuristics. We conjecture that the L-approach always finds optimum packings of (?, w)-rectangles into rectangular pieces. Moreover, the approach may also be useful when dealing with cutting and packing problems involving L-shaped pieces.     

New lower bounds for the three-dimensional finite bin packing problem

The three-dimensional finite bin packing problem (3BP) consists of determining the minimum number of large identical three-dimensional rectangular boxes, bins, that are required for allocating without overlapping a given set of three-dimensional rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. We propose new lower bounds for the problem where the items have a fixed orientation and then we extend these bounds to the more general problem where for each item the subset of rotations by 90° allowed is specified. The proposed lower bounds have been evaluated on different test problems derived from the literature. Computational results show the effectiveness of the new lower bounds.     

A fast algorithm for two-dimensional pallet loading problems of large size

This paper concerns the two-dimensional pallet loading problem (PLP), which requires the determination of the orthogonal layout that loads the maximum number of identical small rectangles (i.e., boxes or products) onto a large rectangle (i.e., pallet or container) without overlapping. Although many algorithms have been developed for this problem, the large amount of time required to find efficient layouts for a large PLP presents great practical difficulties. In this paper, we develop a heuristic that finds efficient layouts with low complexity. We also propose a new algorithm, using the heuristic as a sub-algorithm, which rapidly finds complicated solutions having a 5-block structure. Finally, computational results show that the new algorithm can be successfully applied to large PLPs with sizes exceeding 6800 boxes.     

Analysis of a multi-category classifier

The use of boxes for pattern classification has been widespread and is a fairly natural way in which to partition data into different classes or categories. In this paper we consider multi-category classifiers which are based on unions of boxes. The classification method studied may be described as follows: find boxes such that all points in the region enclosed by each box are assumed to belong to the same category, and then classify remaining points by considering their distances to these boxes, assigning to a point the category of the nearest box. This extends the simple method of classifying by unions of boxes by incorporating a natural way (based on proximity) of classifying points outside the boxes. We analyze the generalization accuracy of such classifiers and we obtain generalization error bounds that depend on a measure of how definitive is the classification of training points.     

The design of composite permutations with applications to DES-like S-boxes

This paper presents an iterative construction method for building composite permutations. Its efficiency is based on the concepts of pre-computation and equivalence classes. Equivalence class representatives of permutations on four bits are pre-computed. These class representatives can serve as input to the construction method, however, the results are also of independent interest for applications in cryptography. A well-known example of a cryptosystem using composite permutations for its Substitution boxes (S-boxes) is the Data Encryption Standard (DES). Throughout the paper, DES-like S-boxes are defined as mappings satisfying all design criteria as disclosed by one of the designers of DES. All permutations on four bits with DES-like properties are identified. Starting with pre-computed representatives of classes with such permutations, two iterations of a specialized version of the algorithm are applied to obtain bounds on the minimum differential uniformity and minimum non-linear uniformity of DES-like S-boxes. It is established that the two values cannot be less than eight, and that DES-like S-boxes for which the values are both equal to 12 do exist. In addition, if the non-linear uniformity of each of the four permutations in a DES-like S-box is at most six, as in all DES S-boxes, then its non-linear uniformity cannot be less than ten and its minimum differential uniformity equals 12.     

An exact algorithm for the pallet loading problem

The two-dimensional packing problem of finding optimal layouts for identical rectangular boxes on a rectangular pallet has interested OR practitioners for many years. The problem is NP-complete and solution methods to date tend to be heuristic. This paper discusses the development of an exact tree search algorithm based on a graph-theoretic model of the problem.     

A MIP-based slicing heuristic for three-dimensional bin packing

The mixed-case palletization problem is a common problem in warehousing and logistics where boxes of rectangular shapes are stacked on top of each other to form pallets. The problem shares common features with three-dimensional bin packing but requires boxes to be adequately supported. We propose a mixed integer programming formulation that maximizes the density of the bottom layers and the compactness of the pallet to ensure stability for top layers. We use a relative-position formulation with slicing that minimizes height, maximizes the fill rate of slices, and pushes boxes towards the vertical axis in order to consolidate fragmented space. Apart from common non-overlap and dimension-related constraints, we explicitly model the fill rates and force lower slices to have an equal or higher density than upper slices. As expected, the formulation could only handle small instances. To tackle larger instances, we embedded the formulation in an iterative approach that packs subsets of boxes sequentially. The approach was found to provide stable pallets and to outperform the branch-and-bound approach of Martello et al. (Oper Res 48(2):256–267, 2000).     

Free actions on handlebodies

The equivalence (or weak equivalence) classes of orientation-preserving free actions of a finite group G on an orientable three-dimensional handlebody of genus g?1 can be enumerated in terms of sets of generators of G. They correspond to the equivalence classes of generating n-vectors of elements of G, where n=1+(g−1)/|G|, under Nielsen equivalence (or weak Nielsen equivalence). For Abelian and dihedral G, this allows a complete determination of the equivalence and weak equivalence classes of actions for all genera. Additional information is obtained for other classes of groups. For all G, there is only one equivalence class of actions on the genus g handlebody if g is at least 1+?(G)|G|, where ?(G) is the maximal length of a chain of subgroups of G. There is a stabilization process that sends an equivalence class of actions to an equivalence class of actions on a higher genus, and some results about its effects are obtained.     

Dynamic multi-dimensional bin packing

A natural generalization of the classical online bin packing problem is the dynamic bin packing problem introduced by Coffman et al. (1983) [7]. In this formulation, items arrive and depart and the objective is to minimize the maximal number of bins ever used over all times. We study the oriented multi-dimensional dynamic bin packing problem for two dimensions, three dimensions and multiple dimensions. Specifically, we consider dynamic packing of squares and rectangles into unit squares and dynamic packing of three-dimensional cubes and boxes into unit cubes. We also study dynamic d-dimensional hypercube and hyperbox packing. For dynamic d-dimensional box packing we define and analyze the algorithm NFDH for the offline problem and present a dynamic version. This algorithm was studied before for rectangle packing and for square packing and was generalized only for multi-dimensional cubes. We present upper and lower bounds for each of these cases.     

Practical Considerations of the Pallet-Loading Problem

The pallet-loading problem, in which a number of identical boxes are to be packed orthogonally onto a rectangular pallet, has been the subject of several algorithms in recent years. These algorithms are concerned with maximizing the number of boxes fitted. In this paper, consideration is given to the development of loading patterns into pallet stacks, and criteria which might be applied to determine the suitability of these stacks for storage and transportation. A technique is developed which allows the stability and clampability of stacks to be tested, and this is applied to layouts produced by the recent algorithm of Bischoff and Dowsland. The relative importance of different criteria is illustrated and shown to have implications for the structure of algorithms that are to provide acceptable pallet stacks.     

Universal graphs and induced-universal graphs

We construct graphs that contain all bounded-degree trees on n vertices as induced subgraphs and have only cn edges for some constant c depending only on the maximum degree. In general, we consider the problem of determining the graphs, so-called universal graphs (or induced-universal graphs), with as few vertices and edges as possible having the property that all graphs in a specified family are contained as subgraphs (or induced subgraphs). We obtain bounds for the size of universal and induced-universal graphs for many classes of graphs such as trees and planar graphs. These bounds are obtained by establishing relationships between the universal graphs and the induced-universal graphs.     

A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint

The article presents a tree search algorithm (TRSA) for the strip packing problem in two and three dimensions with guillotine cutting constraint. In the 3D-SPP a set of rectangular items (boxes) and a container with fixed width and height but variable length are given. An arrangement of all boxes within the container has to be determined so that the required length is minimised. The 2D-SPP is analogously defined. The proposed TRSA is based on a tree search algorithm for the container loading problem by Fanslau and Bortfeldt (INFORMS J. Comput. 22:222?C235, 2010). The TRSA generates guillotine packing patterns throughout. In a comparison with all recently proposed 3D-SPP methods the TRSA performs very competitive. Fine results are also achieved for the 2D-SPP.     

Some counting questions for matrices with restricted entries

We obtain upper bounds for the number of arbitrary and symmetric matrices with integer entries in a given box (in an arbitrary location) and a given determinant. We then apply these bounds to estimate the number of matrices in such boxes which have an integer eigenvalues. Finally, we outline some open questions.     

New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem

The two-dimensional orthogonal non-guillotine cutting stockproblem (NGCP) appears in many industries (e.g. the wood andsteel industries) and consists of cutting a rectangular mastersurface into a number of rectangular pieces, each with a givensize and value. The pieces must be cut with their edges alwaysparallel to the edges of the master surface (orthogonal cuts).The objective is to maximize the total value of the pieces cut. New upper bounds on the optimal solution to the NGCP are described.The new bounding procedures are obtained by different relaxationsof a new mathematical formulation of the NGCP. Various proceduresfor strengthening the resulting upper bounds and reducing thesize of the original problem are discussed. The proposed newupper bounds have been experimentally evaluated on test problemsderived from the literature. Comparisons with previous boundingprocedures from the literature are given. The computationalresults indicate that these bounds are significantly betterthan the bounds proposed in the literature.     

Distances between classes in $$W^{1,1}(\Omega ;{\mathbb {S}}^{1})$$

We introduce an equivalence relation on the space \(W^{1,1}(\Omega ;{\mathbb {S}}^1)\) which classifies maps according to their “topological singularities”. We establish sharp bounds for the distances (in the usual sense and in the Hausdorff sense) between the equivalence classes. Similar questions are examined for the space \(W^{1,p}(\Omega ;{\mathbb {S}}^1)\) when \(p>1\).