The best requirement to relax, in my opinion, is that of optimality (which, incidentally, is a strong reason to be an adaptation executor rather than a utility maximizer!). My professional research is into optimization heuristics that just focus on getting good solutions and not worrying if they're the best ones- which allows tackling problems that are immensely larger. For many problems, it's simply not worth the time to ensure that no better solution exists- it's a lot of effort for little payout.