A branch-and-bound algorithm for the two-dimensional vector packing problem

Research output: Contribution to journalArticleAcademicpeer-review

47 Citations (Scopus)

Abstract

The two-dimensional vector packing (2DVP) problem can be stated as follows. Given are N objects, each of which has two requirements. The problem is to find the minimum number of bins needed to pack all objects, where the capacity of each bin equals 1 in both requirements. A heuristic adapted from the first fit decreasing rule is proposed, and lower bounds for optimal solutions to the 2DVP problem are investigated. Computing one of these lower bounds is shown to be equivalent to computing the largest number of vertices of a clique of a 2-threshold graph (which can be done in polynomial time). These lower bounds are incorporated into a branch-and-bound algorithm, for which some limited computational experiments are reported.

Original languageEnglish
Pages (from-to)19-25
Number of pages7
JournalComputers & Operations Research
Volume21
Issue number1
DOIs
Publication statusPublished - 1994
Externally publishedYes

Fingerprint

Dive into the research topics of 'A branch-and-bound algorithm for the two-dimensional vector packing problem'. Together they form a unique fingerprint.

Cite this