Abstract Discrete and combinatorial optimization problems such as routing, scheduling, and resource allocation present high computational complexity, limiting the effectiveness of classical exact optimization methods. Most existing metaheuristic (MH) algorithms are originally designed for continuous domains and require transformation procedures that often degrade performance when applied to discrete problems. This study introduces the discrete puma optimizer (DPO), a new variant metaheuristic algorithm developed to operate directly within discrete search spaces by employing discrete-specific operators and adaptive exploration–exploitation strategies. DPO is applied to 7 real-world optimization problems, including the Traveling Salesman Problem, Smart Grid Optimization, Factory Production Planning, Vehicle Routing Problem, Modern TSP, Team Orienteering Problem, and Electric Vehicle Charging Station Location Optimization, and evaluated on a total of 22 small-, medium-, and large-scale dataset instances. The performance of DPO is benchmarked against 9 various and well-known MH algorithms. Experimental results show that DPO attains superior best and mean solutions, lower variance, and faster stabilization in convergence behavior. Wilcoxon signed-rank tests confirm the statistical significance of the observed improvements, particularly in large-scale scenarios where competing methods show marked degradation. Comprehensive cross-problem rankings further illustrate DPO’s enhanced generalizability and scalability. These results position DPO as an effective and robust approach for real-world large-scale discrete optimization tasks.