Reducing the number of needed primers in multiplex polymerase chain reaction experiments is useful, or even essential, in large scale genomic research. In this paper, we transform this multiple-use primer design problem into a set-covering problem, and propose a modified compact genetic algorithm (MCGA) approach to disclose optimal solutions. Our experimental results demonstrate that MCGA effectively reduces the primer numbers of multiplex PCR experiments among whole-genome data sets of four test species within a feasible computation time, especially when applied on complex genomes. Moreover, the performance of MCGA further exhibits better global stability of optimal solutions than conventional heuristic methods that may fall into local optimal traps. © Springer-Verlag 2004.