Efficiency of self-optimizing systems is heavily dependent on their optimization strategies, e.g., choosing exact or approximate solver. A choice of such a strategy, in turn, is influenced by numerous factors, such as re-optimization time, size of the problem, optimality constraints, etc. Exact solvers are domain-independent and can guarantee optimality but suffer from scaling, while approximate solvers offer a "good-enough" solution in exchange for a lack of generality and parameter-dependence. In this paper we discuss the trade-offs between exact and approximate optimizers for solving a quality-based software selection and hardware mapping problem from the scalability perspective. We show that even a simple heuristic can compete with thoroughly developed exact solvers under condition of an effective parameter tuning. Moreover, we discuss robustness of the obtained algorithm's configuration. Last but not least, we present a software product line for parameter tuning, which comprise the main features of this process and can serve as a platform for further research in the area of parameter tuning.