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.展开更多
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.展开更多
The numerical mode of nonlinear wave transformation based on both the Laplace equation for water field and the Bernoulli equation for water surface is a kind of time-domain boundary problem with initial conditions. An...The numerical mode of nonlinear wave transformation based on both the Laplace equation for water field and the Bernoulli equation for water surface is a kind of time-domain boundary problem with initial conditions. And the basis for establishing the numerical mode of nonlinear wave in time domain is to trace the position of wave free surface and to calculate the instantaneous surface height and surface potential function. This paper firstly utilizes the ‘0-1' combined BEM to separate the boundary by means of discretization of Green's integral equation based on the Laplace equation, then separates the free surface of wave with FEM and derives the FEM equation of wave surface that satisfies the nonlinear boundary conditions. By jointly solving the above BEM and FEM equations, the wave potential and surface height could be obtained with iteration in time domain. Thus a new kind of nonlinear numerical mode is established for calculating wave transformation. The wave test in the numerical wave tank shows that the numerical simulation with this mode is of high accuracy.展开更多
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.展开更多
SUN Da-peng BAO Wei-bin, WU Hao and LI Yu-cheng （ In this paper the 0-1 combined BEM is adopted to subdivide the computational domain boundary, and to discretize the Green＇s integral expression based on Laplace equ...SUN Da-peng BAO Wei-bin, WU Hao and LI Yu-cheng （ In this paper the 0-1 combined BEM is adopted to subdivide the computational domain boundary, and to discretize the Green＇s integral expression based on Laplace equation. The FEM is used to subdivide the wave surface and deduce the surface equation which satisfies the nonlinear boundary conditions on the surface. The equations with potential function and wave surface height as an unknown quantity by application of Taylor expansion approach can be solved by iteration within the time step. In m-time iteration within the computational process of time step （n-1）At to nat, the results of the previous iteration are taken as the initial value of the two-order unknown terms in the present iteration. Thus, an improved tracking mode of nonlinear wave surface is estabIished, and numerical results of wave tank test indicate that this mode is improved obviously and is more precise than the previous numerical model which ignored the two-order unknown terms of wave surface location and velocity potential function in comparison with the theoretical values.展开更多
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.
基金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.
文摘The numerical mode of nonlinear wave transformation based on both the Laplace equation for water field and the Bernoulli equation for water surface is a kind of time-domain boundary problem with initial conditions. And the basis for establishing the numerical mode of nonlinear wave in time domain is to trace the position of wave free surface and to calculate the instantaneous surface height and surface potential function. This paper firstly utilizes the ‘0-1' combined BEM to separate the boundary by means of discretization of Green's integral equation based on the Laplace equation, then separates the free surface of wave with FEM and derives the FEM equation of wave surface that satisfies the nonlinear boundary conditions. By jointly solving the above BEM and FEM equations, the wave potential and surface height could be obtained with iteration in time domain. Thus a new kind of nonlinear numerical mode is established for calculating wave transformation. The wave test in the numerical wave tank shows that the numerical simulation with this mode is of high accuracy.
文摘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 (Grant No. 50921001)
文摘SUN Da-peng BAO Wei-bin, WU Hao and LI Yu-cheng （ In this paper the 0-1 combined BEM is adopted to subdivide the computational domain boundary, and to discretize the Green＇s integral expression based on Laplace equation. The FEM is used to subdivide the wave surface and deduce the surface equation which satisfies the nonlinear boundary conditions on the surface. The equations with potential function and wave surface height as an unknown quantity by application of Taylor expansion approach can be solved by iteration within the time step. In m-time iteration within the computational process of time step （n-1）At to nat, the results of the previous iteration are taken as the initial value of the two-order unknown terms in the present iteration. Thus, an improved tracking mode of nonlinear wave surface is estabIished, and numerical results of wave tank test indicate that this mode is improved obviously and is more precise than the previous numerical model which ignored the two-order unknown terms of wave surface location and velocity potential function in comparison with the theoretical values.
基金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.
