Two Branch And Bound Algorithms For A Class Of Linear Multiplicative Programming Problem

The linear multiplicative programming problem is a class of non-convex optimization problems.This problem generally contains many local optimal points that are not globally optimal solution which increase the dificulty of solving the problems,so,problem(LMP)is NP-haxd.It is widely used in fields such as financial optimization,economy,engineering,network flows and so on.It contains general quadratic programming,bilinear programming and linear 0-1 programming whidi has attrsacted the curiosity of scholars.For this reason,many algorithms are proposed to solve tlhis kind of problem.In this paper,two branch and bound algorithms are proposed for the linear multiplicative programming problem by combining different linearization techniques.Firstly,for the model to be studied in this paper,the application background and theoretical significance are given.Otherwise,the research status of this model and the main work of this paper are briefly introduced.Secondly,a branch and bound algorithm is proposed for the linear multiplicative programming problem.Based on equivalent transformation of model,branch rules,new linear relaxation techniques and reduction techniques are proposed.And a branch and bound algorithm is constructed by combining with branch and bound framework.Convergence of the algorithm is proved by means of the subsequent solutions of a series of linear programming problems.And the maximum iterations of the algorithm are given by utilizing the feature of the branching process.Finally,numerical computational results show the feasibility and efficiency of the proposed algorithm.Finally,a branch and bound algorithm is proposed for the linear multiplicative programming problem.The problem is transformed into an equivalent programming problem by introducing p auxiliary variables.And,using the special structure of equivalent problem,a novel linear relaxation technique is presented for deriving the linear relaxation programming of equivalent problem,which has separable characteristics and can be used to acquire the upper bound of the optimal value to the problem.Then,a branch and bound algorithm is developed for solving the problem.Finally,The convergence of this algorithm is proved,and the complexity analysis of the algorithm is given.Numerical results are reported to illustrate the feasibility and efficiency of this algorithm.