An improved bilevel programming approach for assortment and cut of defective stocks.

We consider a real assortment-and-cut problem, arising in the glass industry, that
calls for fulfilling some known demand of small rectangular items by cutting only a
restricted variety of rectangular plates. The material to be cut is prone to defects
that can reduce the quality of the product or even cause the loss of some items.
Two recent studies investigated approaches to minimize the impact of random
defects that may hit the plates. One of these proposes a bilevel optimization model
to maximize the expected faultless production, where defect occurrence is simulated
by an adversary that can place at most one random defect in each plate. The leader’s
recourse to this action consists in modifying, when possible, the pattern layout so
that the defect falls in the scrap area and the value of the items lost is minimized.
A good feature of this model is that it can be reduced to a single-level integer
program. However, the approach is on one hand too conservative as the distribution
of defects, following a drastic worst-case perspective, results too particular to be
likely; on the other hand, it is too restrictive, as it postulates no more than one
defect per plate.
We propose an improved bilevel programming formulation that preserves the
desirable reduction property and outdoes the aforementioned limitations. Computational
experiments on realistic instances are presented to highlight the benefits
achieved by the improved approach and to study the viability of the method.