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 .
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.展开更多
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.展开更多
Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems a...Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems are encountered in optimization models involving economies of scale. In this paper, a new hybrid dynamic programming method was proposed for solving concave resource allocation problems. A convex underestimating function was used to approximate the objective function and the resulting convex subproblem was solved with dynamic programming technique after transforming it into a 0-1 linear knapsack problem. To ensure the convergence, monotonicity and domain cut technique was employed to remove certain integer boxes and partition the revised domain into a union of integer boxes. Computational results were given to show the efficiency of the algorithm.展开更多
In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above...In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above quadratic0-1 programming and its relaxed problem, k-coloring problem is converted intoa class of (continuous) nonconvex quadratic programs, and several theoreticresults are also introduced. Thirdly, linear programming approximate algorithmis quoted and verified for this class of nonconvex quadratic programs. Finally,examining problems which are used to test the algorithm are constructed andsufficient computation experiments are reported.展开更多
It is well known that general 0-1 programming problems are NP-Complete and their optimal solutions cannot be found with polynomial-time algorithms unless P=NP. In this paper, we identify a specific class of 0-1 progra...It is well known that general 0-1 programming problems are NP-Complete and their optimal solutions cannot be found with polynomial-time algorithms unless P=NP. In this paper, we identify a specific class of 0-1 programming problems that is polynomially solvable, and propose two polynomial-time algorithms to find its optimal solutions. This class of 0-1 programming problems commits to a wide range of real-world industrial applications. We provide an instance of representative in the field of supply chain management.展开更多
Obnoxious facilities are those crucial to human living, yet antagonistic to the public or environment. However, the interactions between obnoxious facilities and their clients have been less frequently investigated. A...Obnoxious facilities are those crucial to human living, yet antagonistic to the public or environment. However, the interactions between obnoxious facilities and their clients have been less frequently investigated. A state-of-the-art model for this problem involves numerous 0 - 1 variables, rendering it difficult to solve. This study aims at removing most of these 0 - 1 variables to enhanced model efficiency. A compact model is presented in this study, with the equivalence between the new and original models proved. Additionally, numerical tests were conducted to show that the proposed compact model is more efficient than the original one.展开更多
Mathematical programming problems with semi-continuous variables and cardinality constraint have many applications,including production planning,portfolio selection,compressed sensing and subset selection in regressio...Mathematical programming problems with semi-continuous variables and cardinality constraint have many applications,including production planning,portfolio selection,compressed sensing and subset selection in regression.This class of problems can be modeled as mixed-integer programs with special structures and are in general NP-hard.In the past few years,based on new reformulations,approximation and relaxation techniques,promising exact and approximate methods have been developed.We survey in this paper these recent developments for this challenging class of mathematical programming problems.展开更多
文摘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 .
文摘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.
基金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.
基金Project supported by the National Natural Science Foundation oChina (Grant os.79970107 and 10271073)
文摘Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems are encountered in optimization models involving economies of scale. In this paper, a new hybrid dynamic programming method was proposed for solving concave resource allocation problems. A convex underestimating function was used to approximate the objective function and the resulting convex subproblem was solved with dynamic programming technique after transforming it into a 0-1 linear knapsack problem. To ensure the convergence, monotonicity and domain cut technique was employed to remove certain integer boxes and partition the revised domain into a union of integer boxes. Computational results were given to show the efficiency of the algorithm.
文摘In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above quadratic0-1 programming and its relaxed problem, k-coloring problem is converted intoa class of (continuous) nonconvex quadratic programs, and several theoreticresults are also introduced. Thirdly, linear programming approximate algorithmis quoted and verified for this class of nonconvex quadratic programs. Finally,examining problems which are used to test the algorithm are constructed andsufficient computation experiments are reported.
基金supported by National Natural Science Foundation of China (Grant Nos.70471008, 70971072)
文摘It is well known that general 0-1 programming problems are NP-Complete and their optimal solutions cannot be found with polynomial-time algorithms unless P=NP. In this paper, we identify a specific class of 0-1 programming problems that is polynomially solvable, and propose two polynomial-time algorithms to find its optimal solutions. This class of 0-1 programming problems commits to a wide range of real-world industrial applications. We provide an instance of representative in the field of supply chain management.
文摘Obnoxious facilities are those crucial to human living, yet antagonistic to the public or environment. However, the interactions between obnoxious facilities and their clients have been less frequently investigated. A state-of-the-art model for this problem involves numerous 0 - 1 variables, rendering it difficult to solve. This study aims at removing most of these 0 - 1 variables to enhanced model efficiency. A compact model is presented in this study, with the equivalence between the new and original models proved. Additionally, numerical tests were conducted to show that the proposed compact model is more efficient than the original one.
基金supported by the National Natural Science Foundation of China grants(Nos.11101092,10971034)the Joint National Natural Science Foundation of China/Research Grants Council of Hong Kong grant(No.71061160506)the Research Grants Council of Hong Kong grants(Nos.CUHK414808 and CUHK414610).
文摘Mathematical programming problems with semi-continuous variables and cardinality constraint have many applications,including production planning,portfolio selection,compressed sensing and subset selection in regression.This class of problems can be modeled as mixed-integer programs with special structures and are in general NP-hard.In the past few years,based on new reformulations,approximation and relaxation techniques,promising exact and approximate methods have been developed.We survey in this paper these recent developments for this challenging class of mathematical programming problems.
