Core instances for testing: A case study

Core instances for testing: A case study

0.00 Avg rating0 Votes
Article ID: iaor20062222
Country: Netherlands
Volume: 166
Issue: 1
Start Page Number: 51
End Page Number: 62
Publication Date: Oct 2005
Journal: European Journal of Operational Research
Authors: ,
Keywords: scheduling, optimization
Abstract:

Data generation for computational testing of optimization algorithms is a key topic in experimental algorithmics. Recently, concern has arisen that many published computational experiments are inadequate with respect to the way test instances are generated. In this paper we suggest a new research direction that might be useful to cope with the possible limitations of data generation. The basic idea is to select a finite set of instances which ‘represent’ the whole set of instances. We propose a measure of the representativeness of an instance, which we call ε-representativeness: for a minimization problem, an instance xε is ε-representative of another instance x if a (1 + ε)-approximate solution to x can be obtained by solving xε. Focusing on a strongly NP-hard single machine scheduling problem, we show how to map the infinite set of all instances into a finite set of ε-representative core instances. We propose to use this finite set of ε-representative core instances to test heuristics.

Reviews

Required fields are marked *. Your email address will not be published.