Popular software used in research is incorrectly reporting solution is optimal: what to do? I have an example demonstrating the solution produced by a popularly used software package is not the optimal solution, despite the software claiming that it is. Several recent papers published from my lab have used this software in their evaluations, and I know it is extensively used in the research community to solve optimization problems.

So I am unsure how to report this bug; it is a proprietary, closed-source software. As a first step, I could contact the software developer about the bug, although they don't seem to have a straightforward method to report bugs. 

But a larger issue is that papers published with results based upon a buggy software could be compromised. What if the eventual fix causes the software to take much longer to execute, so that running on large instances is now infeasible?

I have told my advisor about the issue, but he does not seem very interested, possibly because of the potential ramifications.

I am currently working on a project where I could have used this software; I now don't trust it and have switched to a much less powerful open-source alternative. So I guess my question is: how should I handle this situation?
You should create a reproducible test case that demonstrates the flaw conclusively.  If you are that confident and the software is that widely used, it warrants publication in a technical journal. They key is to involve the company. Show them your test case and mention you have interest in publishing the result. Offer to collaborate with them on the publication. That way, they will be forced to either demonstrate you are wrong or admit you are right. In the latter case, they save face by admitting the problem. If they ignore you, press ahead.