A Branch and Bound Algorithm for solving the 2D Strip Packing Problem

Abdelghani Bekrar (1) , Imed Kacem (1) , Chengbin Chu (1) , Cherif Sadfi (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

In this paper we consider the two dimensional strip packing problem with guillotine cuts. The problem consists on packing a set of rectangular items on one strip of width W and infinite height. The items packed without overlapping, must be extracted by a series of cuts that go from one edge to the opposite edge (guillotine constraint). For this problem, we give a new lower bound based on decomposing the set of the items in sub-sets. This lower bound is used in a branch and bound algorithm to solve the problem to optimality. Computational results are presented to show the performance of both the lower bound and the exact algorithm

Keywords: Strips; Textile industry; Approximation algorithms; Upper bound; Testing

Domains: Computer Science [cs]; Operations Research [cs.RO]; Computer Science [cs]; Data Structures and Algorithms [cs.DS]

Abdelghani Bekrar, Imed Kacem, Chengbin Chu, Cherif Sadfi. A Branch and Bound Algorithm for solving the 2D Strip Packing Problem. 2006 International Conference on Service Systems and Service Management, Oct 2006, Troyes, France. pp.940-946, ⟨10.1109/ICSSSM.2006.320758⟩. ⟨hal-02473352⟩