A unified method for a class of convex separable nonlinear knapsack problems

被引：15

作者：

Zhang, Bin ^{[1
]}

Hua, Zhongsheng ^{[1
]}

机构：

[1] Univ Sci & Technol China, Sch Management, Anhua 230026, Peoples R China

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2008年 / 191卷 / 01期

基金：

中国国家自然科学基金; 高等学校博士学科点专项科研基金;

关键词：

nonlinear knapsack problem; convex programming; separable programming; singly constrained program;

D O I：

10.1016/j.ejor.2007.07.005

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, a unified algorithm is proposed for solving a class of convex separable nonlinear knapsack problems, which are characterized by positive marginal cost (PMC) and increasing marginal loss-cost ratio (IMLCR). By taking advantage of these two characteristics, the proposed algorithm is applicable to the problem with equality or inequality constraints. In contrast to the methods based on Karush-Kuhn-Tucker (KKT) conditions, our approach has linear computation complexity. Numerical results are reported to demonstrate the efficacy of the proposed algorithm for different problems. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：1 / 6

页数：6

共 23 条

[1] Exact, approximate, and generic iterative models for the multi-product Newsboy problem with budget constraint [J].

Abdel-Malek, L ;

Montanari, R ;

Morales, LC .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2004, 91 (02) :189-198

[2] COMPUTATIONAL COMPARISON AMONG 3 MULTICOMMODITY NETWORK FLOW ALGORITHMS [J].

ALI, A ;

HELGASON, R ;

KENNINGTON, J ;

LALL, H .

OPERATIONS RESEARCH, 1980, 28 (04) :995-1000

[3] DISAGGREGATION AND RESOURCE-ALLOCATION USING CONVEX KNAPSACK-PROBLEMS WITH BOUNDED VARIABLES [J].

BITRAN, GR ;

HAX, AC .

MANAGEMENT SCIENCE, 1981, 27 (04) :431-441

[4]

Brethauer K. M., 1995, ORSA Journal on Computing, V7, P109, DOI 10.1287/ijoc.7.1.109

[5]

BRETTHAUER K, 1994, DECISION SCI, V25, P561, DOI 10.1111/j.1540-5915.1994.tb01860.x

[6] Nonlinear integer programming for optimal allocation in stratified sampling [J].

Bretthauer, KM ;

Ross, A ;

Shetty, B .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 116 (03) :667-680

[7] The nonlinear knapsack problem - algorithms and applications [J].

Bretthauer, KM ;

Shetty, B .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 138 (03) :459-472

[8] THE NONLINEAR RESOURCE-ALLOCATION PROBLEM [J].

BRETTHAUER, KM ;

SHETTY, B .

OPERATIONS RESEARCH, 1995, 43 (04) :670-683

[9] A projection method for the integer quadratic knapsack problem [J].

Bretthauer, KM ;

Shetty, B ;

Syam, S .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1996, 47 (03) :457-462

[10] A pegging algorithm for the nonlinear resource allocation problem [J].

Bretthauer, KM ;

Shetty, B .

COMPUTERS & OPERATIONS RESEARCH, 2002, 29 (05) :505-527

← 1 2 3 →