Vitrification of tank wastes to form glass is a technique that will be used for the disposal of high-level waste at Hanford. The amount of glass produced can be reduced by blending of the wastes. The optimal way to combine the tanks to minimize the volume of glass can be determined from a discrete blend calculation. However, this problem results in a combinatorial explosion as the number of tanks increases. Moreover, the property constraints make this problem highly non-convex where many algorithms get trapped in local minima. In this paper we examine the use of different combinatorial optimization approaches to solve this problem. A two stage approach using a combination of Simulated Annealing and nonlinear programming (NLP) is developed. The results of different methods such as heuristics approach based on human knowledge and judgment, mixed integer nonlinear programming (MINLP) approach with GAMS, and branch and bound with lower bound derived from the structure of the given blending problem are compared with this coupled Simulated Annealing and NLP approach.