On the Solution of Generalized Spectrum Allocation Problems

We consider a spectrum aggregation based spectrum allocation problem (SAP) for coexisting wireless systems: find the maximum number of secondary users whose bandwidth requirements can be satisfied by aggregating (parts of) given spectrum holes. In the classical form, this optimization problem turns out to share a common structure with the one-dimensional skiving stock problem (SSP), where as many (large) items as possible have to be constructed simultaneously by combining (smaller) items of a given supply. However, in practice, the spectrum aggregation is usually restricted by hardware limitations, such as filter technologies, and the capability of controlling interference. These additional constraints separate the considered problem from an ordinary SSP, and represent a new challenge in the field of discrete optimization. This article provides a general introduction to the relations between the SSP and the SAP. Moreover, we will discuss, how practically meaningful extensions of the classical SAP can be tackled from a mathematical point of view. As a main contribution, we exploit some important problem-specific properties to derive tailored solution techniques.