The design of highly multiplex PCR primers to amplify and enrich many different DNA sequences is increasing in biomedical importance as new mutations and pathogens are identified. One major challenge in the design of highly multiplex PCR primer sets is the large number of potential primer dimer species that grows quadratically with the number of primers to be designed. Simultaneously, there are exponentially many choices for multiplex primer sequence selection, resulting in systematic evaluation approaches being computationally intractable. Here, we present and experimentally validate Simulated Annealing Design using Dimer Likelihood Estimation (SADDLE), a stochastic algorithm for design of highly multiplex PCR primer sets that minimize primer dimer formation. Our approach uses a rapidly computable Loss function to approximate the degree of primer dimer formation within a primer set, and randomly swaps primers in the set with alternative candidates using a simulated annealing algorithm. In a 96-plex PCR primer set (192 primers), we show that we can reduce the fraction of primer dimers from 90.7% in a naively designed PCR primer set to 4.9% in our optimized primer set. Running the optimized 96-plex primer set on FFPE DNA samples from cancer patients, we likewise observe a low fraction of primer dimer reads. Even when scaling to 384-plex (768 primers), the PCR primer set designed by our algorithm maintains low primer dimer fraction. In addition to NGS, we also show that our SADDLE-designed multiplex primer sets can be used in qPCR settings to allow highly multiplexed detection of gene fusions in cDNA, with a single-tube assay comprising 60 primers detecting 56 distinct gene fusions recurrently observed in lung cancer.