This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Reilly, C. H.

Synthetic Optimization Problem Generation: Show Us the Correlations!

College of Engineering and Computer Science, University of Central Florida, Orlando, Florida 32816
creilly{at}mail.ucf.edu

In many computational experiments, correlation is induced between certain types of coefficients in synthetic (or simulated) instances of classical optimization problems. Typically, the correlations that are induced are only qualified—that is, described by their presumed intensity. We quantify the population correlations induced under several strategies for simulating 0–1 knapsack problem instances and also for correlation-induction approaches used to simulate instances of the generalized assignment, capital budgeting (or multidimensional knapsack), and set-covering problems. We discuss implications of these correlation-induction methods for previous and future computational experiments on simulated optimization problems.

Key words: random variable generation; correlation; 0–1 knapsack problem; generalized assignment problem; capital budgeting problem; set-covering problem
History: received March 2002; revised February 2009; accepted March 2009.