A splitting algorithm for simulation-based optimization problems with categorical variables

Z. Nedělková, C. Cromvik, P. Lindroth, M. Patriksson, A-B Strömberg. Engineering Optimization, Volume 51, Issue 5, 2019, 815-831. Online 30 July, 2018.


In the design of complex products, some product components can only be chosen from a finite set of options. Each option then corresponds to a multidimensional point representing the specifications of the chosen components. A splitting algorithm that explores the resulting discrete search space and is suitable for optimization problems with simulation-based objective functions is presented. The splitting rule is based on the representation of a convex relaxation of the search space in terms of a minimum spanning tree and adopts ideas from multilevel coordinate search. The objective function is underestimated on its domain by a convex quadratic function. The main motivation is the aim to find—for a vehicle and environment specification—a configuration of the tyres such that the energy losses caused by them are minimized. Numerical tests on a set of optimization problems are presented to compare the performance of the algorithm developed with that of other existing algorithms.

Photo credits: Nic McPhee