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 .
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 .
基金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)安徽省人才基金资助。