Properties of synthetic optimization problems

Author

Reilly, Charles H.

Author_Institution

Dept. of Ind. Eng. & Manage. Sci., Central Florida Univ., Orlando, FL, USA

Volume

1

fYear

1998

fDate

13-16 Dec 1998

Firstpage

617

Abstract

We present an approach for measuring certain properties of synthetic optimization problems based on the assumed distribution of coefficient values. We show how to estimate the proportion of all possible solutions that are feasible for the 0-1 Knapsack Problem. We calculate the population variance of the possible solution values and assess the impact of objective constraint correlation on the variability of feasible solution values. We also show how inter-constraint correlation affects the proportion of feasible solutions in the 2-dimensional Knapsack Problem. Finally, we discuss the significance of our findings for designers of computational experiments

Keywords

constraint theory; knapsack problems; optimisation; 0-1 Knapsack Problem; 2-dimensional Knapsack Problem; assumed distribution; coefficient values; computational experiment design; feasible solution values; inter-constraint correlation; objective constraint correlation; population variance; solution values; synthetic optimization problems; variability; Character recognition; Design optimization; Distributed computing; Engineering management; Industrial engineering; Optimization methods; Performance evaluation; Random number generation; Testing;

fLanguage

English

Publisher

ieee

Conference_Titel

Simulation Conference Proceedings, 1998. Winter

Conference_Location

Washington, DC

Print_ISBN

0-7803-5133-9

Type

conf

DOI

10.1109/WSC.1998.745042

Filename

745042