| The work in this dissertation examines combinatorial problems from a probabilistic approach in an effort to improve existing solution methods or find new algorithms that perform better. Applications addressed here are focused on military uses such as weapon-target assignment, path planning and multisensor multitarget tracking; however, these may be easily extended to the civilian environment.; A probabilistic analysis of combinatorial problems is a very broad subject; however, the context here is the study of input data and solution values.; We investigate characteristics of the mean optimal solution values for random multidimensional assignment problems (MAPS) with axial constraints. Cost coefficients are taken from three different random distributions: uniform, exponential and standard normal. In the cases where cost coefficients are independent uniform or exponential random variables, experimental data indicate that the average optimal value of the MAP converges to zero as the MAP size increases. We give a short proof of this result for the case of exponentially distributed costs when the number of elements in each dimension is restricted to two. In the case of standard normal costs, experimental data indicate the average optimal value of the MAP goes to negative infinity as the MAP size increases. Using curve fitting techniques, we develop numerical estimates of the mean optimal value for various sized problems. The experiments indicate that numerical estimates are quite accurate in predicting the optimal solution value of a random instance of the MAP.; Using a novel probabilistic approach, we provide generalized proofs of the asymptotic characteristics of the mean optimal costs of MAPS. The probabilistic approach is then used to improve the efficiency of the popular greedy randomized adaptive search procedure.; As many solution approaches to combinatorial problems rely, at least partly, on local neighborhood searches, it is widely assumed the number of local minima has implications on solution difficulty. We investigate the expected number of local minima for random instances of the MAP. We report on empirical findings that the expected number of local minima does impact the effectiveness of three different solution algorithms that rely on local neighborhood searches.; A probabilistic approach is used to develop an MAP test problem generator that creates difficult problems with known unique solutions. |
