An Evolutionary Algorithm for Column Generation in Integer Programming: An Effective Approach for 2D Bin Packing

International audienceWe 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