In two-dimensional cutting problems, length and width are relevant for the cutting patterns generation, regarding both the raw-material and the pieces to cut. This is the case of: the home-textile industry, where rectangular shapes are cut from fabric rolls to be later assembled in bed sheets, duvet bags and pillow covers; the garment industry, where irregular (polygonal) shapes (trouser parts, shirt sleeves, collars and other apparel parts) are cut from fabric rolls; but also the furniture and metalware industries, where two-dimensional components have to be cut from larger boards.

However, adding one dimension to the problem is not just incremental, regarding the one-dimensional problem. When dealing with two-dimensions complex geometric problems have to be solved. It is not just a question of deciding from which raw-material object to cut each small piece, which is already a NP-hard problem, but now the exact position of each small piece on the plan has to be decided, so that pieces do not overlap and are fully contained inside the larger raw-material object. Even when dealing with the simpler case where all shapes are rectangles, the geometric constraints add an extraordinary difficulty to the cutting problem resolution. When the pieces are represented by more complex polygonal shapes (nesting problem, aka irregular packing problem), checking and ensuring the geometric feasibility of a cutting pattern is as hard as the combinatorial problem.

This task will look at the problem that arises in the home-textile industry, i.e. cutting rectangles from fabric rolls. In this real-world application, the main source of uncertainty arises from unexpected defects in the fabric that can run for dozens or hundreds of meters. In practice this defects narrow the usable width of the roll, meaning that an important part of the defective roll can still be used, but not only the rectangular small pieces that were supposed to be cut from this section of the roll are not actually cut, as also a new usage for the defective section has to be devised.

These unexpected changes not only question the optimality of the generated solutions but also require replanning and modifying cutting patterns. The goal of this task is to incorporate this type of uncertainty in the two-dimensional cutting problem so that solutions are more robust regarding the variability induced by uncertainty and, when replanning is needed, the changes in the already defined cutting plans are minimized: robust planning and optimized replanning.