  The irregular strip-packing problem, also known as nesting or marker making,
is defined as the automatic computation of a non-overlapping placement of a set
of non-convex polygons onto a rectangular strip of fixed width and unbounded
length, such that the strip length is minimized. Nesting methods based on
heuristics are a mature technology, and currently, the only practical solution
to this problem. However, recent performance gains of the Mixed-Integer
Programming (MIP) solvers, together with the known limitations of the
heuristics methods, have encouraged the exploration of exact optimization
models for nesting during the last decade. Despite the research effort, the
current family of exact MIP models for nesting cannot efficiently solve both
large problem instances and instances containing polygons with complex
geometries. In order to improve the efficiency of the current MIP models, this
work introduces a new family of continuous MIP models based on a novel
formulation of the NoFit-Polygon Covering Model (NFP-CM), called NFP-CM based
on Vertical Slices (NFP-CM-VS). Our new family of MIP models is based on a new
convex decomposition of the feasible space of relative placements between
pieces into vertical slices, together with a new family of valid inequalities,
symmetry breakings, and variable eliminations derived from the former convex
decomposition. Our experiments show that our new NFP-CM-VS models outperform
the current state-of-the-art MIP models. Finally, we provide a detailed
reproducibility protocol and dataset based on our Java software library as
supplementary material to allow the exact replication of our models,
experiments, and results.
