Yeah, for sure. I mean, it's often the case (as I've found in my own research) that even relatively unsophisticated heuristics will often nail the global optimum for a good number of problems.
Here's one particular example: I tried what is essentially a greedy heuristic on a physical design problem (a problem where we design a device such that an excited wave within it best matches a specific shape). I had earlier showed that solving the general problem is NP-hard.
The objective value the greedy heuristic returned? .589. It took <100ms to compute this.
Now, I rewrote the problem in a way that was amenable to a mixed-integer convex problem solver (which involved some somewhat-complicated reductions because the problem isn't easily phrased in this way). Put it on Mosek (which is a pretty fast solver) and let it run.
The globally-certified optimal value (to <1%)? .587. Mosek took two and a half hours to find this.
So, tl;dr, the problem was "hard enough" that a branch-and-bound solver took a long time to solve, but still "easy enough" that a basic heuristic might as well have nailed the global optimum.
-----
I think the reason such papers keep popping up (and I see them around surprisingly often) is that people really don't realize how good basic heuristics really can be!
Here's one particular example: I tried what is essentially a greedy heuristic on a physical design problem (a problem where we design a device such that an excited wave within it best matches a specific shape). I had earlier showed that solving the general problem is NP-hard.
The objective value the greedy heuristic returned? .589. It took <100ms to compute this.
Now, I rewrote the problem in a way that was amenable to a mixed-integer convex problem solver (which involved some somewhat-complicated reductions because the problem isn't easily phrased in this way). Put it on Mosek (which is a pretty fast solver) and let it run.
The globally-certified optimal value (to <1%)? .587. Mosek took two and a half hours to find this.
So, tl;dr, the problem was "hard enough" that a branch-and-bound solver took a long time to solve, but still "easy enough" that a basic heuristic might as well have nailed the global optimum.
-----
I think the reason such papers keep popping up (and I see them around surprisingly often) is that people really don't realize how good basic heuristics really can be!