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.