
Nesting problems are twodimensional cutting and packing problems involving irregular shapes. This thesis
is focused on real applications on Nesting problems such as the garment industry or the glass cutting. The
aim is to study different mathematical methodologies to obtain good lower bounds by exact procedures and
upper bounds by heuristic algorithms. The core of the thesis is a mathematical model, a Mixed Integer
Programming model, which is adapted in each one of the parts of the thesis.
This study has three main parts: first, an exact algorithm for Nesting problems when rotation for the
pieces is not allowed; second, an Iterated Greedy algorithm to deal with more complex Nesting problems
when pieces can rotate at several angles; third, a constructive algorithm to solve the twodimensional irregular
bin packing problem with guillotine cuts. This thesis is organized as follows.
The first part is focused on developing exact algorithms. In Chapter 2 we present two Mixed Integer
Programming (MIP) models, based on the Fischetti and Luzzi MIP model. We consider horizontal
lines in order to define the horizontal slices which are used to separate each pair of pieces. The second model,
presented in Section 2.3, uses the structure of the horizontal slices in order to lift the bound constraints.
Section 2.5 shows that if we solve these formulations with CPLEX, we obtain better results than the formulation
proposed by Gomes and Oliveira. The main objective is to design a Branch and Cut algorithm
based on the MIP, but first a Branch and Bound algorithm is developed in Chapter 3. Therefore, we study
different branching strategies and design an algorithm which updates the bounds on the coordinates of the
reference point of the pieces in order to find incompatible variables which are fixed to 0 in the current branch
of the tree. The resulting Branch and Bound produces an important improvement with respect to previous
algorithms and is able to solve to optimality problems with up to 16 pieces in a reasonable time.
In order to develop the Branch and Cut algorithm we have found several classes of valid inequalities.
Chapter 4 presents the different inequalities and in Chapter 5 we propose separation algorithms for some
of these inequalities. However, our computational experience shows that although the number of nodes is
reduced, the computational time increases considerably and the Branch and Cut algorithm becomes slower.
The second part is focused on building an Iterated Greedy algorithm for Nesting problems. In Chapter
6 a constructive algorithm based on the MIP model is proposed. We study different versions depending on
the objective function and the number of pieces which are going to be considered in the initial MIP. A new
11
idea for the insertion is presented, trunk insertion, which allows certain movements of the pieces already
placed. Chapter 7 contains different movements for the local search based on the reinsertion of a given
number of pieces and compaction. In Chapter 8 we present a mathheuristic algorithm, which is an Iterated
Greedy algorithm because we iterate over the constructive algorithm using a destructive algorithm. We have
developed a local search based on the reinsertion of one and two pieces. In the constructive algorithm, for
the reinsertion of the pieces after the destruction of the solution and the local search movements, we use several
parameters that change along the algorithm, depending on the time required to prove optimality in the
corresponding MIP models. That is, somehow we adjust the parameters, depending on the difficulty of the
current MIP model. The computational results show that this algorithm is competitive with other algorithms
and provides the best known results on several known instances.
The third part is included in Chapter 9. We present an efficient constructive algorithm for the two
dimensional irregular bin packing problem with guillotine cuts. This problem arises in the glass cutting
industry. We have used a similar MIP model with a new strategy to ensure a guillotine cut structure. The
results obtained improve on the best known results. Furthermore, the algorithm is competitive with state of
the art procedures for rectangular bin packing problems.
