<p>The Minimum Capacitated Dominating Set (CAPMDS) problem involves finding a dominating set with the minimum cardinality, subject to the constraint that each vertex in the dominating set cannot dominate more vertices than its associated capacity allows. CAPMDS is a crucial variant of the dominating set problem and finds applications in various domains, including wireless sensor networks and information retrieval. While researchers have devoted significant attention to CAPMDS, existing approaches often struggle to scale up and can be time-consuming. In this study, we aim to enhance the scalability and efficiency of solving the CAPMDS problem. We introduce a novel multi-start algorithm with an iterated decremental local search (MSIDLS) that incorporates several innovative concepts. Firstly, we develop an adaptive initialization process with varying degrees of greediness to generate an initial solution. Subsequently, an iterated decremental local search is executed to improve the initial solution, consistently reducing the solution’s cardinality. Notably, we introduce a dynamic vertex weighting score function with a forgetting mechanism to assess the suitability of inserting or removing a vertex from the dominating set. Furthermore, we present a new reallocation strategy based on the constraint path within the iterated decremental local search, intensifying the quality of the solution. To validate our approach, we conduct experiments on large graphs with both uniform and variable capacity. The computational results demonstrate that MSIDLS outperforms state-of-the-art algorithms, consistently achieving superior best and average objective values. Our experiments on large graphs also verify the effectiveness of the reallocation strategy and the score function with forgetting.</p>