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.展开更多
In this paper, the problem of program performance scheduling with accepting strategy is studied. Considering the uncertainty of actual situation, the duration of a program is expressed as a bounded interval. Firstly, ...In this paper, the problem of program performance scheduling with accepting strategy is studied. Considering the uncertainty of actual situation, the duration of a program is expressed as a bounded interval. Firstly, we decide which programs are accepted. Secondly, the risk preference coefficient of the decision maker is introduced. Thirdly, the min-max robust optimization model of the uncertain program show scheduling is built to minimize the performance cost and determine the sequence of these programs. Based on the above model, an effective algorithm for the original problem is proposed. The computational experiment shows that the performance’s cost (revenue) will increase (decrease) with decision maker’s risk aversion.展开更多
文摘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.
基金国家自然科学基金( 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)安徽省人才基金资助。
基金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.
文摘In this paper, the problem of program performance scheduling with accepting strategy is studied. Considering the uncertainty of actual situation, the duration of a program is expressed as a bounded interval. Firstly, we decide which programs are accepted. Secondly, the risk preference coefficient of the decision maker is introduced. Thirdly, the min-max robust optimization model of the uncertain program show scheduling is built to minimize the performance cost and determine the sequence of these programs. Based on the above model, an effective algorithm for the original problem is proposed. The computational experiment shows that the performance’s cost (revenue) will increase (decrease) with decision maker’s risk aversion.
