Local Search For The Bin Packing Problem

. The bin packing problem consists in finding the minimum number of bins of given capacity which are necessary to pack a certain number of itens. In this work, we propose an improvement procedure for the bin packing problem, based on the progressive reduction of the number of bins used by a previously constructed solution. Since bin eliminations often lead to unfeasible solutions, a local search feasibility operator based on the differencing method for number partition is used. Encouraging computational results on benchmark instances are reported. Key words. Combinatorial optimization, bin packing, local search, differencing method 1. Introduction. Given a set of n items with weights w i ; i = 1; : : : ; n associated with each of them, the classical bin packing problem consists in finding the minimum number of bins of capacity b necessary to pack the items. Alternatively, the problem may also be seen as that of partitioning the items into a minimum number of subsets, such that the sum ..