An extended pattern search algorithm for three-dimensional component layout

An extended pattern search algorithm is introduced for efficient component layout optimization. The algorithm is applicable to general layout problems , where component geometry can be arbitrary, design goals can be multiple a nd spatial constraint satisfactions can be of different types. Extensions t o pattern search are introduced to help the algorithm to converge to optima l solutions by escaping inferior local minima. The performance on all of th e test problems shows that the algorithm runs one-to-two orders of magnitud e faster than a robust simulated annealing- based algorithm for results wit h the same quality. The algorithm is further extended to solve a concurrent layout and renting problem, which demonstrates the ability of the algorith m to apply new pattern strategies in search and to include different object ive functions in optimization. [S1050-0472(00)01901-2].