The multiplex polymerase chain reaction (MP-PCR) is a quick and inexpensive technique in molecular biology for amplifying multiple DNA loci in a single Polymerase Chain Reaction (PCR). One of the criteria to achieve highly specific reaction products is to keep the concentration of the amplification primers low. In research, the dilemma associated with primer minimization for MP-PCR reactions has been formulated as the Multiple Degenerate Primer Selection Problem (MDPSP). MDPSP is related to the earlier Degenerate Primer Design (DPD) problem that has proven to be NP-complete. This paper formulates a new, so far, unexplored variant, the Multiple Degenerate Primer Selection Problem with Errors (MDPSPE) and introduces new algorithms for solving this new version. Furthermore, we implement an exact algorithm, DPS-HDR for solving the earlier MDPSP and compare the algorithm's performance on randomly generated data sets with DPS-HD, thus far the most efficient algorithm for solving MDPSP introduced in [2]. We expect to reduce the execution time of the algorithm in comparison to DPS-HD. © 2009 IEEE.