It's hard to specify one approach because it depends on your needs. From my experience I can suggest the following:
Typical solvers report solutions as "optimal" using gap parameters specifying relative and absolute differences. Take this CPLEX parameter as an example: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/EpGap.html
You can use this in two ways:
If you don't know if your problem is solvable in practice, i.e., constraints are not contradictory in a non-obvious way, just set the precision to lowest possible value and try to solve the problem. The solver should just find anything meeting the constraints practically ignoring the cost function.
Next, when you know that the problem is solvable, you can tighten the constraints. In your example you mention the number of people, first you can start with $x+10$ and if it works you then decrease it to $x+5$ and so on. By doing so you can easily estimate which set of parameters and constraints you can further optimize.
The question is whether you need the highest possible precision or maybe you can bend the rules and consider using less "optimal" solution. This can highly speed up the calculations, i.e., in my problems I was able to find the solution in seconds instead of hours by switching gap from $0.0001$ to $0.01$ in Gurobi.
Hard constraints and soft constraints
Common approach is to change some of the constraints to constraints with penalty. For instance, instead of saying that $x < 10$ you say that $x - p < 10$ where $p \ge 0$. Next, you add $p$ to your cost function with big negative multiplier. Such a variable splitting can help finding solutions in case of infeasibility, what's more, if you report the solutions during calculations you can use them to get better approximations of the constraints you can drop to get better results. It looks like this is something you already considered and this is a common approach.
Depending on the type of your problem, you may be able to divide it into multiple phases and calculate the solutions in parallel. Using this method with "sanity tests" method mentioned above you can still have some solution in case when your most wanted model is not feasible.
Example: if you are optimizing for two "realms" (like number of people and number of tasks), try to set some value manually and optimize the other value for that case. By doing this you make the model much easier so you can calculate multiple of them.
Simplify the model
It sounds easy but in fact can be very hard. Make sure that you don't perform unnecessary difficult operations (like calculating GCD or multiplying variables). Look for easier formulations including constraints moved to cost function (i.e, instead of calculating the minimum of a set and them maximizing it with the cost function, use min-max trick). Make sure that you have smallest possible domains (especially for so-called "big $M$" variables). Also, check your floating point precision.
Just deal with it
Sometimes you just can't mitigate it, after all it might not be solvable in any acceptable time. You can consider calculating different problem (i.e., completely different approach) or use different algorithm at all (neural nets, simulated annealing etc).