Identifying alternate optimal solutions to the design approximation problem in stock cutting

The design approximation problem is a well known problem in stock cutting, where, in order to facilitate the optimization techniques used in the cutting process, it is required to approximate complex designs by simpler ones. Although there are algorithms available to solve this problem, they all suffer from an undesirable feature that they only produce one optimal solution to the problem, and do not identify the complete set of all optimal solutions. The focus of this paper is to study this hitherto unexplored aspect of the problem: specifically, the case is considered in which both the design and the parent material are convex shapes, and some essential properties of all optimal solutions to the design approximation problem are ascertained. These properties are then used to devise two efficient schemes to identify the set of all optimal solutions to the problem. Finally, the recovery of a desired optimal approximation from the identified sets of optimal solutions is discussed.