Robust single-stage selection problems with budgeted uncertainty

We study single-stage decision problems in which a subset of items with minimum total cost has to be selected at once from a given set of items, subject to two costs of each item – fixed and uncertain – and cardinality constraints for each cost type. The worst-case budgeted uncertainty is considered. At the time of decision making, the fixed costs are known, but for each uncertain cost, only the range of its values is available. Similar but two-stage selection problems have been studied in the literature, in which first- and second-stage decisions are made before and after uncertain costs become known, respectively. The single-stage problems studied are distinguished by continuous or discrete uncertain costs, and by uncertainty budgets based on cardinality (number of uncertain costs deviating from smallest nominal values) or volume (total uncertain cost increase). An almost complete computational complexity classification is provided, including fast polynomial-time algorithms, NP- and Σ 2 p -completeness and hardness proofs.