Global Optimization Algorithm For Several Kinds Of Integer Programming Problems

In actual production and life,many integer optimization problems can be solved by establishing corresponding mathematical models.However,due to most of the problems have multiple local optimal solutions,especially the nonlinear integer programming problem,due to the nature of the nonlinearity of the objective function and/or the nonlinearity of the constraints,it is relatively difficult to solve global optimization problems.So far,there is no unified method for solving these kinds of problems effectively.The form and structure of problems will greatly affect the results.Therefore,it is of great significance to study methods of solving such problems.In this thesis,two kinds of solving methods are given based on the model of several kinds of integer programming problems,the filled function method and the branch and bound method.The main work has been done are listed as follows:(1)Recently,many filled functions contain parameters that are not easy to adjust.In order to overcome the disadvantages,this section constructs a new parameter free filling function for the bounded constraint integer programming problem.In addition,to make the problem minimized from any point,some improvements are made to the discrete steepest descent method.The numerical results show that the algorithm can find the global optimal solution from any point,and compared with other literature,the average computation time and the average calculation in algorithm complexity.(2)For general integer programming problem,a simple unary function is added to judge whether the point satisfies the constraint condition,the constraint problem is transformed into an equivalent problem.At the same time,a filled function with one parameter is constructed,the numerical results proved the algorithm is effective.(3)For the separable concave integer programming problem,this section constructs a linear lower approximate function by using the convex envelope of the problem,the lower bounds and upper bounds of the problem are obtained by solving the linear underestimating the objective function,then we propose an improved branch method--largest distance bisection technique,it divides rectangle into two sub-rectangle,Numerical tests on problems show that the proposed algorithm is efficient.(4)For the separable D.C.programming problem,the objective function can be converted to the sum of convex function and concave function,and and the lower bounds are obtained by the relaxation linear programming of the original problem.Then,the largest distance bisection method is used to solve the problem until the optimal solution is found.Finally,several numerical examples are given to show that the algorithm is feasible.