Parametric models of local search progression

Algorithms that search for good solutions to optimization problems present a trace of current best objective values over time. We describe an empirical study of parametric models of this progression that are both interesting as ways to characterize the search progression compactly and useful as means of predicting search behavior. In our computational experiments, we give examples of a variety of problems and algorithms where we are able to use the parametric models to make predictions of performance that cross instances and instance sizes.