In this paper we propose optimization algorithms for the runtime management of gracefully degradable adaptive MP-SoCs. Assuring the reliability of all hardware components in a system becomes increasingly difficult. On top of the growing defect densities and rising complexity of conventional testing, wear-out effects may reduce the availability of on-chip resources during system lifetime. However, adaptability of modern MPSoCs can provide the means for permanent fault tolerance and graceful degradation via runtime system management. We have developed custom heuristics as well as tailored existing optimization techniques (simulated annealing and genetic algorithm), to deliver a fast and efficient response to unpredictable loss of system resources. We have emulated the resulting runtime manager on the Intel Single-Chip Cloud Computer (SCC), an experimental chip multiprocessor developed by Intel Labs. Comparison of the different algorithms in terms of solution quality and response time, and the scaling of their response time with the size of problem input, indicate that our custom heuristics are faster by at least one order of magnitude, but simulated annealing and genetic algorithm are more consistent in dealing with constraints to the allowed solutions, e.g. limited system reconfiguration time. All algorithms scale well, since their response time, in almost every case, grows sub-linearly with respect to the input size.