For pure bin packing problems some really good heuristics exist. For the problem illustrated in http://www.developerfusion.com/article/5540/bin-packing/ one of the best solutions is:
So if we solve to optimality, do we gain a lot? From http://en.wikipedia.org/wiki/Bin_packing_problem is looks doubtful. Indeed when I solve:
we get an optimal solution with 17 bins.
Of course as discussed in http://yetanothermathprogrammingconsultant.blogspot.com/2011/07/scheduling-of-tv-advertisement-theory.html my real models are almost always much more complicated than shown in these stylized bin packing examples. In those cases a MIP-based solution algorithm can be even more worthwhile than a (simple) heuristic as there is more room for improvement. In the real case we dealt with a complicated multi-objective model where our model seems to outperform the heuristic in almost all objectives. This is the case even after the heuristic was improved using some fine-tuning after looking at our solutions.