2004 •
An Evolutionary Algorithm for Column Generation in Integer Programming: An Effective Approach for 2D Bin Packing
Authors:
Jakob Puchinger, Günther R. Raidl
Abstract:
International audience; We consider the 3-stage two-dimensional bin packing problem , which occurs in real-world problems such as glass cutting. For it, we present a new integer linear programming formulation and a branch and price algorithm. Column generation is performed by applying either a greedy heuristic or an Evolutionary Algorithm (EA). Computational experiments show the benefits of the EA-based approach. The higher computational effort of the EA pays off in terms of better final solutions; furthermore more instances can be solved to pr (...)
International audience; We consider the 3-stage two-dimensional bin packing problem , which occurs in real-world problems such as glass cutting. For it, we present a new integer linear programming formulation and a branch and price algorithm. Column generation is performed by applying either a greedy heuristic or an Evolutionary Algorithm (EA). Computational experiments show the benefits of the EA-based approach. The higher computational effort of the EA pays off in terms of better final solutions; furthermore more instances can be solved to provable optimality. (Read More)
We have placed cookies on your device to help make this website and the services we offer better. By using this site, you agree to the use of cookies. Learn more