Improved Penalties for the Branch and Bound Algorithm

Improved penalty calculation for the branch and bound algorithm, as applied to mixed integer programming problems, are presented. For a given variable, finding the best (“up” or “down”) penalty requires solving a mixed integer program. When relaxed, this becomes a knapsack problem, the solution of which is a lower bound on the best penalty. Applying a modified marginal analysis approach yields a lower bound on this. Nevertheless, the resulting penalty is at least as good as the commonly used simple penalty and an improved penalty of Tomlin. Little additional computation is needed.