The webpage supplements to the research paper:
Qian Hu, Wenbin Zhu*, Andrew Lim, Hu Qin. A branch-and-price algorithm for the two-dimensional vector packing problem with piecewise linear cost function. European Journal of Operational Research. 2017, 260 (1): 70-80
The two-dimensional vector packing problem with piecewise linear cost function (2DVPP-PLC) models a practical packing problem faced by many companies that use courier services. We propose a branch-and-price algorithm to solve the 2DVPP-PLC exactly. The column generation procedure is a key component that affects the performance of a branch-and-price algorithm. The pricing problem exhibits an interesting structure that allows us to decompose it into subproblems that form a lattice. We explore dominance relations on the lattice and design an efficient algorithm for the pricing problem. Experimental results show that our branch-and-price algorithm is capable of solving 2DVPP-PLC test instances effectively.
The algorithms were implemented in Java. The experimental results reported in this section were obtained on a Linux workstation equipped with an Intel Xeon E5-1603 CPU clocked at 2.80 gigahertz, 8 gigabytes of RAM, and running CentOS 6.0. The integer programming solver used was ILOG CPLEX 16.3 (64-bit edition). For each test 2DVPP-PLC instance, a time limit of 3600 CPU seconds is set. For each test 2DVPP instance, a time limit of 600 CPU seconds is set.
2DVPP test instances: http://or.dei.unibo.it/library/two-constraint-bin-packing-problem
2DVPP-PLC test instances: https://drive.google.com/open?id=0B7azD5PrlaaNcV95UXFqWkl2dFU
Tables: https://drive.google.com/open?id=0B7azD5PrlaaNMHc4OE5WYWNPVmM
Appendix: https://drive.google.com/open?id=0B7azD5PrlaaNaFNwb1F0UnVfVkk