Title

Synthetic Optimization Problem Generation: Show Us the Correlations!

Authors

Authors

C. H. Reilly

Abbreviated Journal Title

INFORMS J. Comput.

Keywords

random variable generation; correlation; 0-1 knapsack problem; generalized assignment problem; capital budgeting problem; set-covering; problem; 0-1 KNAPSACK-PROBLEM; GENERALIZED ASSIGNMENT PROBLEM; SINGLE-MACHINE; ALGORITHMS; PERFORMANCE; BOUNDS; Computer Science, Interdisciplinary Applications; Operations Research &; Management Science

Abstract

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.

Journal Title

Informs Journal on Computing

Volume

21

Issue/Number

3

Publication Date

1-1-2009

Document Type

Article

Language

English

First Page

458

Last Page

467

WOS Identifier

WOS:000268558800009

ISSN

1091-9856

Share

COinS