My company makes a living by algorithmically finding solutions to complex applied mathematical problems.
Theoretically, the best thing to do is to find an optimal solution to the problem -even if it is a local optimum- as this means that you can stop looking for more.
However, in practice, the user in many cases will not care whether the algorithm will approximate the optimal solution a few more decimal places; what matters is that the solution does not have any major drawbacks, so that it can be safely used for its intended purpose; and that it is better of what one expert could find in the same time by hand. That's the reason why approximate algorithms are used so often.
Under those constraints, you're better off with an anytime algorithm with a good heuristic, which gives a viable good-enough suboptimal solution fast, and which can be left running while the expert analyzes the best solution found so far, to decide if it is acceptable.
Theoretically, the best thing to do is to find an optimal solution to the problem -even if it is a local optimum- as this means that you can stop looking for more.
However, in practice, the user in many cases will not care whether the algorithm will approximate the optimal solution a few more decimal places; what matters is that the solution does not have any major drawbacks, so that it can be safely used for its intended purpose; and that it is better of what one expert could find in the same time by hand. That's the reason why approximate algorithms are used so often.
Under those constraints, you're better off with an anytime algorithm with a good heuristic, which gives a viable good-enough suboptimal solution fast, and which can be left running while the expert analyzes the best solution found so far, to decide if it is acceptable.