Exact Methods For Multi-objective Integer Non-linear Programming Problem

Many real-world problems are multi-objective integer non-linear programming(MINLP)problems.MINLP is one kind of multi-objective integer programming(MIP)problems with at least one non-linear objective function or constraint.MINLP is not exactly solved yet,because of its non-linearity,it cannot be solved with optimization software like CPLEX.All the research about solving method for MINLP are approximation algorithms,the only method could be used to exactly solve MINLP is the traditional ?-constraint method,but it cannot guarantee the obtained solution is Pareto-optimal.The requirement of time and space to solve MINLP will increase dramaticly with the increasing amount of objectives and feasible solutions of MINLP.Research about the exact algorithms for MINLP in this paper aims to propose exact and fast algorithms for MINLP,the main contents are as following.(1)Proposing exact algorithms for MINLP firstly.To guarantee the obtained solution is Pareto-optimal,basic ?-constraint method is proposed through improving the traditional ?-constraint method.The time complexity of the basic ?-constraint method is O(pM2N),where p,M and N are the numbers of objectives,the Pareto-optimal solutions and the feasible solutions respectively.To decrease the time complexity,improved ?-constraint method is proposed,which time complexity is O(M2N).To decrease the time complexity further more,fast ?-constraint method is proposed by cutting the dominated solutions each time,it can decrease the time complexity to O(pMN).The experiment results show that fast e-constraint method performs dozens of times faster than the basic ?-constraint method.(2)Proposing an algorithm architecture for MINLP by cutting solution space beforehand.The main idea of the architecture is as following:taking the advantage of some special Pareto-optimal solutions that can dominate a large amount of feasible solutions,to cut these dominated feasible solutions firstly,and then finding the left Pareto-optimal solutions using fast ?-constraint method.To implement this algorithm architecture,two special Pareto-optimal solutions and three methods to cut solution space are proposed.The experiment results show that this architecture can reduce about 50%running time.(3)Proposing parallel exact algorithms for MINLP.Taking use of task parallel and data parallel,to make the algorithm architecture by cutting solution space beforehand parallel.The experiment results show that parallel exact algorithms could achieve several times acceleration.