    # Also in the Article

Positions stage for the 2SP
This protocol is extracted from research article:
Exact solutions for the 2d-strip packing problem using the positions-and-covering methodology
PLoS One, Jan 14, 2021;

Procedure

The objective of the Positions stage is to generate the set of valid positions where an item can be placed into the strip, that is, from the infinite set of positions that an item can take in the bin, the P&C determines only a finite set that guarantees the optimality of the solution. The inputs of the Positions stage are i) the number n of items with their specifics width wi, height hi, and demand di, ii) the width W of the strip, and iii) the current height H of the strip (first computed with Eq 1 or a known lower bound, or an updated value).

With the current height H of the strip, the first step in the Positions stage is to delineate a Cartesian grid inside the strip, that is, a regular tessellation of the 2-dimensional Euclidean space by congruent unit squares, where each square has a particular identification. We arbitrarily choose the enumeration that starts at the top left corner square and ends at the bottom right square (see Fig 3a). Thus, for each item, a valid position is created if its top left corner coincides with a tiling, and its width and height dimensions do not exceed the size of the strip. Each valid position is labeled to differentiate one from each other. Fig 3b shows the valid position for an item with dimensions 2 × 3 with its top-left corner at tile 1. Notice that the position which starts in the tile 1 × W would not be a valid position for this item. Let JH be the set of valid positions for all the items for a fixed height H of the strip. To generate JH, we start populating its valid positions width-wise and then length-wise for each item. The size of JH is pseudo-polynomial, but this pre-processing allows the P&C method to decompose the problem and to reach optimal solutions.

a) Grid inside of the strip and b) Valid position for an item with dimensions 2 × 3 with its top-left corner at tile 1.

Fig 4 shows the set of valid positions for an item of 2 × 3 and an item of 5 × 3 in a strip with dimensions 6 × 4. In this case, JH has 14 valid positions. The set from 1 to 10 corresponds for the first item while the set from 11 to 14 to the second item. Each valid position is unique; therefore, it has a specific label and an unrepeatable tiles set. For example, position 1 (corresponding to the 2 × 3 item) contains tiles 1, 2, 3, 5, 6, and 7.

Set JH of valid positions for items of 2 × 3 and 5 × 3 in a strip with H = 6 and W = 4.

The resulting set of valid positions may be view as a correspondence matrix CH = {cjp}, where rows represent the set of valid positions jJH and columns are the tiles in the strip. Matrix CH is composed of 1’s and 0’s, where cjp = 1 if valid position j covers tile p, cjp = 0 otherwise. The correspondence matrix of Fig 4 (set JH for an item of 2 × 3 and another one of 5 × 3 in a strip with H = 6 and W = 4) appears in Table 1. Each row in the correspondence matrix represents the respective valid position presented in Fig 4. For example, row 1 has ones in tiles 1, 2, 3, 5, 6, and 7, which correspond with position 1 of the figure.

Notice that the set of valid positions determined by the unitary grid is sufficient to reach the optimal solution of the 2SP since all input data are integer.

Note: The content above has been extracted from a research article, so it may not display correctly.

Q&A