AbstractUnderfunding and the continuous deterioration of pavement assets have been among the major challenges for transportation agencies in the US. These challenges motivate the use of different optimization techniques such as integer programming to perform maintenance and rehabilitation planning at the network level. However, one of integer programming’s limitations is the massive computational power requirement associated with the large number of solutions searched by the algorithm to get the optimal solution, limiting the size of the network it can optimize. In this paper, the full mathematical derivation of the binary integer programming problem is shown in terms of budget constraints only and in terms of both budget and percentage of poor assets (PPA) constraints. An alternative approach including the PPA constraint is therefore suggested along with a new practical way of reducing the search space based on the statistical bootstrap approach. The proposed approach’s adequacy is validated through a comparison of different optimization approaches applied to a small asphalt concrete (AC) pavement network. The suggested approach shows promising results because it significantly reduced the time required to allocate budget funds over the test network of 400 asphalt concrete (AC) segments.