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.展开更多
0-1 programming is a special case of the integer programming, which is commonly encountered in many optimization problems. Neural network and its general energy function are presented for 0-1 optimization problem. The...0-1 programming is a special case of the integer programming, which is commonly encountered in many optimization problems. Neural network and its general energy function are presented for 0-1 optimization problem. Then, the 0-1 optimization problems are solved by a neural network model with transient chaotic dynamics (TCNN). Numerical simulations of two typical 0-1 optimization problems show that TCNN can overcome HNN's main drawbacks that it suffers from the local minimum and can search for the global optimal solutions in to solveing 0-1 optimization problems.展开更多
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.展开更多
集值折扣{0-1}背包问题(Discounted{0-1}Knapsack Problem with Setup,D{0-1}KPS)指在同一类别中可选择多个项,每个类别对目标函数和约束条件都增加了额外的固定设置成本。提出一种求解D{0-1}KPS的改进动态规划算法,算法针对D{0-1}KPS...集值折扣{0-1}背包问题(Discounted{0-1}Knapsack Problem with Setup,D{0-1}KPS)指在同一类别中可选择多个项,每个类别对目标函数和约束条件都增加了额外的固定设置成本。提出一种求解D{0-1}KPS的改进动态规划算法,算法针对D{0-1}KPS问题本身结构特征,融合多目标优化问题中非支配解集思想,通过利用状态之间的支配与非支配关系,对每个阶段的状态集进行剪枝,形成非支配状态集,从而提出改进动态规划算法。通过实例验证了该算法的有效性和可行性。展开更多
文摘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.
基金This project was supported by the National Natural Science Foundation of China (79970042).
文摘0-1 programming is a special case of the integer programming, which is commonly encountered in many optimization problems. Neural network and its general energy function are presented for 0-1 optimization problem. Then, the 0-1 optimization problems are solved by a neural network model with transient chaotic dynamics (TCNN). Numerical simulations of two typical 0-1 optimization problems show that TCNN can overcome HNN's main drawbacks that it suffers from the local minimum and can search for the global optimal solutions in to solveing 0-1 optimization problems.
基金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.
文摘集值折扣{0-1}背包问题(Discounted{0-1}Knapsack Problem with Setup,D{0-1}KPS)指在同一类别中可选择多个项,每个类别对目标函数和约束条件都增加了额外的固定设置成本。提出一种求解D{0-1}KPS的改进动态规划算法,算法针对D{0-1}KPS问题本身结构特征,融合多目标优化问题中非支配解集思想,通过利用状态之间的支配与非支配关系,对每个阶段的状态集进行剪枝,形成非支配状态集,从而提出改进动态规划算法。通过实例验证了该算法的有效性和可行性。