A BRANCH-AND-BOUND ALGORITHM FOR THE 2-DIMENSIONAL VECTOR PACKING PROBLEM

The two-dimensional vector packing (2DVP) problem can be stated as fol lows. Given are N objects, each of which has two requirements. The pro blem 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 heuri stic adapted from the first fit decreasing rule is proposed, and lower bounds for optimal solutions to the 2DVP problem are investigated. Co mputing one of these lower bounds is shown to be equivalent to computi ng the largest number of vertices of a clique of a 2-threshold graph ( which can be done in polynomial time). These lower bounds are incorpor ated into a branch-and-bound algorithm, for which some limited computa tional experiments are reported.