Gasoline is produced by blending several different components in ratios such that the blended mixture meets the required quality specifications. The blender produces different batches of gasoline by switching operation from one grade of gasoline to another. Blend planning horizon usually spans 10 to 14 days. Blend plan optimization minimizes the total blend costs by solving a multiperiod problem, where demands need to be satisfied in each period and some inventory is carried into the future time periods to meet the demands. Since blend component production is determined by a longer range refinery production plan, inventory carrying costs are not included in the objective function. It is shown that nonlinear programming (NLP) as well as mixed integer nonlinear programming (MINLP) solvers lead to different blend recipes and different blend volume patterns for the same total cost. The new algorithm described in this work systematically searches for multiple optimum solutions; this opens the way for blend planners to select from different blend plans based on additional considerations (e.g., blend more of regular gasoline earlier in the planning horizon thereby creating an opportunity to meet more demand for it in early periods) instead of having to use only one solution that varies with the choice of the solver. Inherent structure of the proposed algorithm makes it well suited for implementation on parallel CPU machines.