[lorenzhs]

That's not entirely true. I'm a PhD student in theoretical computer science and some of my colleagues work on (hyper-)graph partitioning, both of which are NP-complete. For most real-world instances, nobody has any clue what the optimum cut/imbalance/... is. It would be very useful to evaluate the quality of the heuristics, though. A 0.5% improvement is suddenly much more impressive if you can show that you're only half as far from the optimum as your closest competitor. Or are you not seeing any improvement on instance X because whatever you're trying isn't working, or is it because you've already got the optimum?, etc

[lokerfoi]

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.

[naasking]

What's your take on this recent work?

https://www.reddit.com/r/compsci/comments/78yx99/171009278_e...