One of the best public examples is LKH solver for travelling salesman. I'm not familiar with problems for which proving optimality of a solution to a specific p

One of the best public examples is LKH solver for travelling salesman. I'm not familiar with problems for which proving optimality of a solution to a specific problem instance is not accomplished. For example, for travelling salesman and vehicle routing there are many instances with known optimum. Even for those unknown tight bounds are easily achieved.