Résumé
POPMUSIC is a template for creating heuristics specially designed for dealing with large combinatorial problems that can be partially optimized. The basic idea is to optimize sub-parts of solutions until a local optimum is reached. The useful computational effort should be spent for optimizing these sub-parts. However, it is observed in practice that this computational effort grows almost linearly with problem size while the extraction of sub-parts has an higher algorithmic complexity. This work proposes a template for extracting sub-parts also in linear time.