An Improvement Of Pseudo—cost Branch Strategies For Mixed Integer Programming

ABSTRACT:Currently, integer programming has been the one of the most successful optimization methods for solving the problems of the economics and management science. Among these problems, the mixed integer programming (MIP) is becoming more and more common, and Branch and Bound algorithm, Cut Separation algorithm arc two main methods for MIP problems. Between them, Branch and Bound algorithm is more efficient to optimize model and solve it. As its high efficiency, MIP becomes more and more common in the academic and industry, which was put forward by the Land Doig and Dakin in the1960s early firstly. Branch and Bound algorithm is mainly divided into two steps:one is the node selection strategy, the other is the branching strategy. Each of the two strategies has many different methods respectively. This article focuses on the Pseudo-cost branching strategy. Using pseudo-cost method to select a better branching variable to generate the subproblems can find out the optimal solution more quickly. As Pseudo-cost has different definitions, and two common kinds of Pscudo-cost are introduced in the article. The article introduces four methods,but the main innovation of this paper is that we define new Pseudo-cost by multiplying and weighted sum of the two pseudo-costs. In our numerical experiments with matlab, we test our new Pseudo-costs. The better result shows the effectiveness of our new Pseudo-cost.