It is well known that airport security is an important component of homeland security, since airports are highly vulnerable to terrorist attacks. In order to improve the overall security of the domestic airport network, some work studied the budget allocation of domestic airport network protection. They established a minimax optimization model and designed an exact cutting plane algorithm to solve the problem. However, the exact algorithm can not solve large-scale problems in an acceptable time. Hence, this paper designs a heuristic cutting plane algorithm for solving budget allocation of large-scale domestic airport network protection. Finally, numerical experiments are carried out to demonstrate the feasibility and effectiveness of the new algorithm.