Sensitivity analysis of the knapsack problem: an improved result

被引：0

作者：

Belgacem, Tarik ^{[1
]}

Hifi, Mhand ^{[1
,2
]}

机构：

[1] Univ Paris 01, CERMSEM, F-75231 Paris 05, France

[2] Univ Picardie Jules Verne, LaRIA, Amiens, France

来源：

2006 INTERNATIONAL CONFERENCE ON SERVICE SYSTEMS AND SERVICE MANAGEMENT, VOLS 1 AND 2, PROCEEDINGS | 2006年

关键词：

combinatorial optimization; knapsack; optimization; sensitivity analysis;

D O I：

10.1109/ICSSSM.2006.320757

中图分类号：

F [经济];

学科分类号：

02 ;

摘要：

In this paper, we study the sensitivity of the optimum of the Knapsack Problem (KP), to the perturbation of the profit of a subset of items. We mainly establish the upper and lower limits of the sensitivity interval, by improving our previous result [2].

引用

收藏

页码：934 / 939

页数：6

相关论文

共 22 条

[1] AN ALGORITHM FOR LARGE ZERO-ONE KNAPSACK-PROBLEMS [J].

BALAS, E ;

ZEMEL, E .

OPERATIONS RESEARCH, 1980, 28 (05) :1130-1154

[2]

BELGACEM T, 2006, 7 ROADEF FEB LILL FR

[3] Sensitivity analysis for knapsack problems: A negative result [J].

Blair, C .

DISCRETE APPLIED MATHEMATICS, 1998, 81 (1-3) :133-139

[4] DISCRETE-VARIABLE EXTREMUM PROBLEMS [J].

DANTZIG, GB .

OPERATIONS RESEARCH, 1957, 5 (02) :266-277

[5] AN LP-BASED APPROACH TO A 2-STAGE CUTTING STOCK PROBLEM [J].

DECARVALHO, JMV ;

RODRIGUES, AJG .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1995, 84 (03) :580-589

[6] Sensitivity analysis of a greedy heuristic for knapsack problems [J].

Ghosh, D ;

Chakravarti, N ;

Sierksma, G .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 169 (01) :340-350

[7]

GILMORE PC, 1966, OPER RES, V13, P879

[8]

Greenberg HJ, 1998, OPERAT RES COMP SCI, P97

[9] Sensitivity of the optimum to perturbations of the profit or weight of an item in the binary knapsack problem [J].

Hifi, M ;

Mhalla, H ;

Sadfi, S .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2005, 10 (03) :239-260

[10] Exact algorithms for large-scale unconstrained two and three staged cutting problems [J].

Hifi, M .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2001, 18 (01) :63-88