Under ever-increasing budget restrictions, the optimal programming of maintenance, rehabilitation, and reconstruction of pavement networks becomes crucial. This paper provides and tests two computationally effective approaches that, in accordance with proposed problem-reduction techniques, may be used for multi-year programming of large-scale pavement networks. The two approaches are the Holistic approach, which tackles the entire planning period at once, and the Sequential approach, which breaks down the planning period and optimizes the work plan for each year separately. The developed approaches were applied to the 2013 dataset of the Quebec highway network, which consists of approximately 16,000 roadbed centerline miles. The application of the methods to the case study shows that both Sequential and Holistic approaches can be used effectively for planning large-scale networks with a reasonable analysis run time. This study provides insights into the behavior of large-scale networks and helps transportation agencies make more consistent and effective decisions regarding the allocation of limited funds by using the proposed methodology.