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

Research output: Contribution to journalArticleAcademicpeer-review

55 Citations (Scopus)


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
Issue number1
Publication statusPublished - 1994
Externally publishedYes


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