Research On Branch And Bound Algorithm For Three Kinds Of Integer Programming Problems

In real life,the integer programming problem has a wide range of applications.However,it is difficult to solve global optimization problems because of the existence of multiple local minima in most problems.Especially for nonlinear integer programming,the nonlinear term of objective function and constraint function deepens the difficulty of solving the problem.Up to now,there is no widely available solution for solving nonlinear integer programming problems.Branch and bound algorithm,as a typical deterministic global optimization algorithm,is usually capable of global optimization for some integer programming problems.However,according to the current research status,branch and bound algorithms are mostly used in solving continuity optimization problems,while integer programming problems are relatively few.So it is important to study branch and bound algorithm for solving nonlinear integer programming problems.This thesis solves three kinds of problems,integer linear multiplicative programming,sum of integer linear multiplicative programming,sum of integer linear ratios programming,and proposes the effective and feasible branch and bound algorithms.And through the corresponding theoretical analysis to and a series of numerical experiments for verification.The specific contents are as follows:(1)For integer linear multiplicative programming problem,a new linear relaxation branch and bound algorithm is proposed.First,the problem is transformed into an equivalence problem by logarithmic identity.Secondly,a linear relaxation technique is proposed which takes advantage of the monotonicity and concavity of logarithmic functions.Then,based on the framework of branch and bound algorithm,the concrete steps of the new algorithm are given.in which the branch operation adopts the standard dichotomy,in order to fully divide the feasible region.At the same time,the region reduction technology is added to the algorithm,so as to remove the infeasible region to the maximum extent and speed up the algorithm.Finally,the feasibility and effectiveness of the algorithm are verified by numerical experiments,and the complexity analysis is carried out.(2)For sum of integer linear multiplicative programming problems,this paper proposes a specific branch and bound algorithm.First,the problem is transformed into an equivalence problem by adding p variables.Then the upper and lower bounds of each linear function are calculated respectively and the relaxed lower bounds are constructed by the concave-convex envelope of bilinear function.Then based on the framework of branch and bound algorithm combined with branch rules and region reduction technology proposed in Chapter 2,a specific linear relaxation branch and bound algorithm is presented and analyzed theoretically.Finally,numerical experiments show that the new algorithm is feasible and effective.(3)For sum of integer linear ratios programming problems,this paper proposes a new linear relaxation method.Firstly,p auxiliary variables are introduced to obtain the equivalent problem of the original problem.The relaxation lower bound function is constructed by the multiplication rule of linear function.Then,the linear relaxation branch and bound algorithm is given and analyzed theoretically.Finally,the feasibility and effectiveness of the proposed algorithm are verified by numerical experiments.