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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

47 Citaten (Scopus)

Samenvatting

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.

Originele taal-2Engels
Pagina's (van-tot)19-25
Aantal pagina's7
TijdschriftComputers & Operations Research
Volume21
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - 1994
Extern gepubliceerdJa

Vingerafdruk

Duik in de onderzoeksthema's van 'A branch-and-bound algorithm for the two-dimensional vector packing problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit