Exact solutions for the 2d-strip packing problem using the positions-and-covering methodology

Area of Science:

• Operations Research
• Combinatorial Optimization

Background:

• The two-dimensional, non-guillotine restricted, strip packing problem is a classical NP-hard problem.
• Objective is to minimize the height of a strip with fixed width and infinite height, given a set of rectangular items.

Purpose of the Study:

• To develop an exact methodology for solving the 2D strip packing problem.
• To obtain optimal solutions for instances where the optimal solution was previously unknown.

Main Methods:

• The Positions and Covering methodology, a two-stage procedure.
• Stage 1: Pseudo-polynomial generation of valid item positions.
• Stage 2: Set-covering formulation to select the optimal item configuration.

Main Results:

• The methodology yields exact solutions for the strip packing problem.
• Experimental results validate the quality and effectiveness for small to medium-sized instances.
• Optimal solutions were found for previously unsolved literature instances.

Conclusions:

• The Positions and Covering methodology is a powerful approach for the 2D strip packing problem.
• This method advances the field by providing optimal solutions for challenging instances.
• The approach demonstrates effectiveness and potential for practical applications.