Computer scientists are always so concerned with optimality. IMO it is sufficient to know an optimum exists and a way to converge on the solution, then finding quasi-optimal solutions is more than good enough.
Not at all. Plenty of people are researching finding satisfiable solution that are quasi-optimal at scale. Once you reach a certain scale of optimization problem, proven optimality in a reasonable time-frame is often infeasible
