Mixed-integer Programming Model for Two-dimensional Non-guillotine Bin Packing Problem with Free Rotation

Two-dimensional bin packing problem (2BPP) is a classical problem in operations research and has been extensively investigated in the past years. The 2BPP can be classified according to choices of the orientation (fixed orientation or 90 degrees rotated) and the cut type (guillotine or non-guillotine cut). Many mathematical models and solution methods have been proposed for the problem. However, due to the difficulty in representing constraints, no exact mathematical model is presented for the two-dimensional non-guillotine bin packing problem with free rotation (2BPP-NR). In this paper, we present two Mixed-integer programming (MIP) models for the 2BPP-NR. Computational experiments are conducted on random problem instances and comparative analyses of the proposed models are presents. Results show the Model II outperforms the Model I in both number of constraints and computational time.