Land managers decide how to allocate resources among multiple threats that can be addressed through multiple possible actions. Additionally, these actions vary in feasibility, effectiveness, and cost. We sought to provide a way to optimize resource allocation to address multiple threats when multiple management options are available, including mutually exclusive options. Formulating the decision as a combinatorial optimization problem, our framework takes as inputs the expected impact and cost of each threat for each action (including do nothing) and for each overall budget identifies the optimal action to take for each threat. We compared the optimal solution to an easy to calculate greedy algorithm approximation and a variety of plausible ranking schemes. We applied the framework to management of multiple introduced plant species in Australian alpine areas. We developed a model of invasion to predict the expected impact in 50 years for each species-action combination that accounted for each species’ current invasion state (absent, localized, widespread); arrival probability; spread rate; impact, if present, of each species; and management effectiveness of each species-action combination. We found that the recommended action for a threat changed with budget; there was no single optimal management action for each species; and considering more than one candidate action can substantially increase the management plan's overall efficiency. The approximate solution (solution ranked by marginal cost-effectiveness) performed well when the budget matched the cost of the prioritized actions, indicating that this approach would be effective if the budget was set as part of the prioritization process. The ranking schemes varied in performance, and achieving a close to optimal solution was not guaranteed. Global sensitivity analysis revealed a threat's expected impact and, to a lesser extent, management effectiveness were the most influential parameters, emphasizing the need to focus research and monitoring efforts on their quantification.