Interconnect materials play the critical role of routing energy and information in integrated circuits. However, established bulk conductors, such as copper, perform poorly when scaled down beyond 10 nm, limiting the scalability of logic devices. Here, a multi-objective search is developed, combined with first-principles calculations, to rapidly screen over 15,000 materials and discover new interconnect candidates. This approach simultaneously optimizes the bulk electronic conductivity, surface scattering time, and chemical stability using physically motivated surrogate properties accessible from materials databases. Promising local interconnects are identified that have the potential to outperform ruthenium, the current state-of-the-art post-Cu material, and also semi-global interconnects with potentially large skin depths at the GHz operation frequency. The approach is validated on one of the identified candidates, CoPt, using both ab initio and experimental transport studies, showcasing its potential to supplant Ru and Cu for future local interconnects.