.png){kind=icon}
.png){kind=icon}
Return
A branch-and-price algorithm for the two-dimensional vector packing problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2019.08.024.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The two-dimensional vector packing problem is a well-known generalization of the classical bin packing problem. It considers two attributes for each item and bin. Two capacity constraints must be satisfied in a feasible packing solution for each bin. The objective is to minimize the number of bins used. To compute optimal solutions for the problem, we propose a new branch-and-price algorithm. A goal cut that sets a lower bound to the objective is used. It is effective in speeding up column generation by reducing the number of iterations. To efficiently solve the pricing problem, we develop a branch-and-bound method with dynamic programming, which first eliminates conflicts between two items through branching, and then solves the two-constraint knapsack problem at leaf nodes through dynamic programming. Extensive computational experiments were conducted based on 400 test instances from existing literature. Our algorithm significantly outperformed the existing branch-and-price algorithms. Most of the test instances were solved within just a few seconds. (C) 2019 Elsevier B.V. All rights reserved.
Keywords:
Packing
Two-dimensional vector packing problem
Exact algorithm
Branch-and-price
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
View more organizations