This work considers the task of finding an AC-Feasible operating point of a severely damaged transmission network while ensuring a minimal amount of active power loads are removed. This AC Minimal Load-Shedding (AC-MLS) task is a non-convex nonlinear optimization problem, which can be incredibly challenging to solve on large-scale transmission system data sets. This work demonstrates that convex relaxations of the AC-MLS problem provide a reliable and scalable method for finding high-quality bounds on the amount of active power load shedding required in the AC-MLS problem. To demonstrate their effectiveness, the solution methods proposed in this work are rigorously evaluated on 1000 N-k scenarios on seven power networks ranging in size from 70 to 6000 buses. The most effective relaxation of the AC-MLS problem converges in less than 20 seconds on commodity computing hardware for all 7000 of the scenarios considered.