Title :
Properties of synthetic optimization problems
Author :
Reilly, Charles H.
Author_Institution :
Dept. of Ind. Eng. & Manage. Sci., Central Florida Univ., Orlando, FL, USA
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;
Conference_Titel :
Simulation Conference Proceedings, 1998. Winter
Conference_Location :
Washington, DC
Print_ISBN :
0-7803-5133-9
DOI :
10.1109/WSC.1998.745042
