The webpage supplements to the research paper:
Lijun Wei, Minghui Lai, Andrew Lim, and Qian Hu*. A branch-and-price algorithm for the two-dimensional vector packing problem. European Journal of Operational Research. 2020, 281(1), 25-35
The two-dimensional vector packing problem is the problem of finding the minimum number of bins to pack all the items, which are given with two attributes (e.g. weight and volume), satisfying that the capacities of each bin in the two dimensions are not violated. The problem arises in packing and scheduling applications. In this work, we propose a new branch-and-price algorithm to solve the problem. A goal cut that introduces a lower bound to the objective is proposed. The cut helps improve the lower bound and reduce the number of iterations in the column generation. A branch-and-bound approach with dynamic programming that first eliminates conflicts among items through branching and then solves the two-constraint knapsack problem at any leaf node using dynamic programming is proposed for the pricing problem. Extensive computational experiments based on 400 test instances with up to 200 items from literature were conducted. Our algorithm outperformed the existing branch-and-price algorithms in literature and reported 5 new best solutions. Most of the test instances were solved in a few seconds.
The proposed algorithm was tested on the 2DVPP test instances from literature. The algorithm was implemented using JAVA programming language. The computational results were obtained on a PC equipped with an Intel(R) Core(TM) i7-6700 CPU clocked at 3.40GHz and 8GB RAM. The integer programming solver used was ILOG CPLEX 12.63 and only a single thread was set. The results can be found online via \url{http://www.computational-logistics.org/orlib/2dvpp/}.