Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are present...Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are presented.The necessary condition is expressed without dual variables.The relations between the global optimal solutions of nonconvex quadratic 0-1 problems and the associated relaxed convex problems are also studied.展开更多
In this paper,quadratic 0-1 programming problem (I) is considered, in terms of its features quadratic 0-1 programming problem is solved by linear approxity heurstic algrothm and a developed tabu search ahgrothm .
In order to optimize the knapsack problem further, this paper proposes an innovative model based on dynamic expectation efficiency, and establishes a new optimization algorithm of 0-1 knapsack problem after analysis a...In order to optimize the knapsack problem further, this paper proposes an innovative model based on dynamic expectation efficiency, and establishes a new optimization algorithm of 0-1 knapsack problem after analysis and research. Through analyzing the study of 30 groups of 0-1 knapsack problem from discrete coefficient of the data, we can find that dynamic expectation model can solve the following two types of knapsack problem. Compared to artificial glowworm swam algorithm, the convergence speed of this algorithm is ten times as fast as that of artificial glowworm swam algorithm, and the storage space of this algorithm is one quarter that of artificial glowworm swam algorithm. To sum up, it can be widely used in practical problems.展开更多
Graph partitioning problem is a classical NP-hard problem.The improvement of graph partitioning results by vertex migration is an important class of methods for graph partitioning.The goal of graph partitioning is get...Graph partitioning problem is a classical NP-hard problem.The improvement of graph partitioning results by vertex migration is an important class of methods for graph partitioning.The goal of graph partitioning is getting a partition with the least number of cut edges,while also satisfying the capacity limit of the partition.In this paper,an optimization model for vertex migration is proposed,considering the influence between neighboring vertices,so that the objective function value of the model is exactly equal to the amount of cut edge variation.The model is converted into a mixed 0-1 linear programming by introducing variables.Then,a heuristic iterative algorithm is designed,in which the mixed 0-1 linear programming model is transformed into a series of small-scale models that contain less integer variables.In the experiment,the method in this paper is simulated and compared with balanced label propagation methods and their related methods.The improvement effect of these methods based on three different initialization methods is analyzed.Extensive numerical experiments on five commonly used datasets validate the effectiveness and efficiency of the proposed method.展开更多
文摘Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are presented.The necessary condition is expressed without dual variables.The relations between the global optimal solutions of nonconvex quadratic 0-1 problems and the associated relaxed convex problems are also studied.
文摘In this paper,quadratic 0-1 programming problem (I) is considered, in terms of its features quadratic 0-1 programming problem is solved by linear approxity heurstic algrothm and a developed tabu search ahgrothm .
文摘In order to optimize the knapsack problem further, this paper proposes an innovative model based on dynamic expectation efficiency, and establishes a new optimization algorithm of 0-1 knapsack problem after analysis and research. Through analyzing the study of 30 groups of 0-1 knapsack problem from discrete coefficient of the data, we can find that dynamic expectation model can solve the following two types of knapsack problem. Compared to artificial glowworm swam algorithm, the convergence speed of this algorithm is ten times as fast as that of artificial glowworm swam algorithm, and the storage space of this algorithm is one quarter that of artificial glowworm swam algorithm. To sum up, it can be widely used in practical problems.
基金supported by the National Key Research and Development Program of China(No.2022YFA1003900).
文摘Graph partitioning problem is a classical NP-hard problem.The improvement of graph partitioning results by vertex migration is an important class of methods for graph partitioning.The goal of graph partitioning is getting a partition with the least number of cut edges,while also satisfying the capacity limit of the partition.In this paper,an optimization model for vertex migration is proposed,considering the influence between neighboring vertices,so that the objective function value of the model is exactly equal to the amount of cut edge variation.The model is converted into a mixed 0-1 linear programming by introducing variables.Then,a heuristic iterative algorithm is designed,in which the mixed 0-1 linear programming model is transformed into a series of small-scale models that contain less integer variables.In the experiment,the method in this paper is simulated and compared with balanced label propagation methods and their related methods.The improvement effect of these methods based on three different initialization methods is analyzed.Extensive numerical experiments on five commonly used datasets validate the effectiveness and efficiency of the proposed method.
基金国家自然科学基金( the National Natural Science Foundation of China under Grant No.30570431)国家高技术研究发展计划( 863)( the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z104)+4 种基金国家教育部新世纪人才支持计划( the New Century Excellent Talent Foundation from MOE of China under Grant No.NCET- 06- 555)安徽省优秀青年基金( No.06042088)安徽省教育厅自然科学( No.2006kj068A No.KJ2007B173)安徽省人才基金资助。
