Lagrangian approach for optimization problems in bin packing.

Bin packing problems (BPP) are finding a position layout for a set of objects inside a container. The optimization objective of this problem can be minimizing the wasted area, maximizing the occupied space, or a group of functions related to the container or objects. The current formulations for these problems need to be more representative of reality's problems. The optimal solutions can be found for small problems. Moreover, formulations are only generalized to represent some possible cases. The approaches to solving these problems depend on specific rules related to the instances of use, a consequence of the complexity of solving a model with these characteristics. For those reasons, it is necessary to emerge a common way to represent these different approaches. So, it is essential to investigate and develop new optimization strategies and representations to obtain better results closer to the industrial needs. This work intends to use a series of well-known tools in operations research but little used in BPP to study packaging problems. This study presents a hybrid method for solving packing problems: This method represents the combination between an exact model and an approximate algorithm. It uses the benefits and strengths of both ways while complementing their weaknesses. Also, we present a general formulation for BPP representing convex objects by their sides (inequalities) or by a set of vertices.