Cost-effective testing of a product in a product line requires obtaining a set of relevant test cases from the entire test suite via test selection and minimization techniques. In this paper, we particularly focus on test minimization for product lines, which identifies and eliminates redundant test cases from test suites in order to reduce the total number of test cases to execute, thereby improving the efficiency of testing. However, such minimization may result in the minimized test suite with low test coverage, low fault revealing capability, low priority test cases, and require more time than the allowed testing budget (e.g., time) as compared to the original test suite. To deal with the above issues, we formulated the minimization problem as a search problem and defined a fitness function considering various optimization objectives based on the above issues. To assess the performance of our fitness function, we conducted an extensive empirical evaluation by investigating the fitness function with three weight-based Genetic Algorithms (GAs) and seven multi-objective search algorithms using an industrial case study and 500 artificial problems inspired from the industrial case study. The results show that Random-Weighted Genetic Algorithm (RWGA) significantly outperforms the other algorithms since RWGA can balance all the objectives together by dynamically updating weights during each generation. Based on the results of our empirical evaluation, we also implemented a tool called TEst Minimization using Search Algorithms (TEMSA) to support test minimization using various search algorithms in the context of product lines.