The Study Of Some Primal Heuristics For Mixed Integer Programming

Mixed Integer Programming(MIP)is widely used in many scientific and en-gineering areas,such as transportation,power dispatching,natural gas distribu-tion,oil mixed flow etc.Studies have shown that 80%of industrial problems are MIP.Therefore,solving MIP has very high value in academic research and prac-tical application.However,MIP is NP-hard while LP is polynomially solvable and general-purpose techniques for its solution are efficient in practice.With the development of computer technology,using the LP computation as a tool,MIP solvers which integrate the branch-and-bound and the cutting plane algorithms are developed.An MIP solver includes presolving,node selection,LP solvers,primal heuristics and so on.When solving MIP,heuristics can find the feasible solution quickly and effectively according to the information provided by the problem itself.In this paper,some primal heuristics are presented and studied,such as rounding heuristics,diving heuristics and OCTANE.Some new ideas in applying OCTANE heuristics are proposed.Finally many many numerical experiments are done to analyze the efficiency of heuristics.The results show that,the efficiency of differ-ent heuristics are different,and the efficiency of calling a variety of heuristics is different from the efficiency of calling just one heuristic.By setting up reasonable calling position and calling frequency,these primal heuristids can find the feasible solution of MIP more quickly and efficiently.