A Hybrid Algorithm with Reduction Criteria for the Bin Packing Problem in One Dimension

In this paper a hybrid algorithm is proposed to find the optimal solution for any instance of the bin packing problem one-dimensional. The hybrid algorithm considers the use of a heuristic method and a mathematical model based on flow arcs technique to find the optimal solution for an instance of 1D-BPP. The hybrid algorithm makes use of the lower bound of an instance as an element that allows it to identify if it have found the optimum or starting from this value it must find the optimal solution. The experiments were performed using the instances of the hard28 set, finding it the optimal solutions for all instances. The results show that the developed algorithm, called AHR, used 75% less time than using the Valerio model.