Popular software used in research is incorrectly reporting solution is optimal: what to do?

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.

The technical answer to the question seems obvious: if there is a clear definition of what "optimum" means for your problems, run both programs and see which one wins, then publish the results.

Any advice on the politics of how to proceed is merely speculation, until you have done the technical work to discover the facts of the case.

These things happen. We once discovered a "schoolboy error" in one of the industry-standard software packages in its field. In the meeting where we presented the results, we had three senior members of the vendor's development team (which totaled about 300 people) sitting with their heads in their hands, knowing full well that if we wanted to we could destroy maybe 75% of their international user base. (Some of the other 25% wouldn't understand what the fuss was about, and ironically their biggest individual customers were likely to be using computer systems where the error didn't occur anyway - which might explain why nobody else had spotted it in the previous 10 years or so).

But there was much more benefit to us in getting the problem fixed rather than nuking the software house, so we went for the "just fix it ASAP" option - and "ASAP" actually took about 2 weeks, to get a beta-test version.

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.

This seems to be a lot of fuss about possibly nothing.

Read the software documentation, if any. It should explain in what cases it declares "solution found". It is usually the case that this indicates that several parameters associated with a necessary condition for optimality are sufficiently small, which indicates that the solution was probably found. No guarantees here.

If you can't find a reason for this behaviour in the documentation, write to the developer with a minimum working example where the unexpected behaviour occurs and ask for clarification.