Upper bounds for the 0-1 stochastic knapsack problem and a B&B algorithm

被引：33

作者：

Kosuch, Stefanie ^{[1
]}

Lisser, Abdel ^{[1
]}

机构：

[1] Univ Paris 11, Rech Informat Lab, F-91405 Orsay, France

来源：

ANNALS OF OPERATIONS RESEARCH | 2010年 / 176卷 / 01期

关键词：

Static stochastic knapsack problems with random weights; Simple recourse; Chance constrained; Expectation constrained; B&B algorithm; Stochastic gradient algorithm; Arrow-Hurwicz; SOCP; APPROXIMATION; OPTIMIZATION;

D O I：

10.1007/s10479-009-0577-5

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper we study and solve two different variants of static knapsack problems with random weights: The stochastic knapsack problem with simple recourse as well as the stochastic knapsack problem with probabilistic constraint. Special interest is given to the corresponding continuous problems and three different problem solving methods are presented. The resolution of the continuous problems allows to provide upper bounds in a branch-and-bound framework in order to solve the original problems. Numerical results on a dataset from the literature as well as a set of randomly generated instances are given.

引用

页码：77 / 93

页数：17

共 34 条

[1]

AGRALI S, 2008, CLASS STOCHASTIC KNA

[2]

ANDRIEU L, 2007, STOCHASTIC PROGRAMMI

[3]

[Anonymous], 2013, Stochastic Programming

[4]

Babaioff M, 2007, LECT NOTES COMPUT SC, V4627, P16

[5]

Boyd S., 2004, CONVEX OPTIMIZATION, VFirst, DOI DOI 10.1017/CBO9780511804441

[6]

BOYD S, 1995, SOFTWARE 2 ORDER CON

[7] AN ALGORITHM FOR MAXIMIZING TARGET ACHIEVEMENT IN THE STOCHASTIC KNAPSACK-PROBLEM WITH NORMAL RETURNS [J].

CARRAWAY, RL ;

SCHMIDT, RL ;

WEATHERFORD, LR .

NAVAL RESEARCH LOGISTICS, 1993, 40 (02) :161-173

[8] A multiobjective metaheuristic for a mean-risk static stochastic knapsack problem [J].

Claro, Joao ;

de Sousa, Jorge Pinho .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2010, 46 (03) :427-450

[9]

Cohn A.M., 1998, P TRIENNIAL S TRANSP

[10] Approximating the stochastic knapsack problem:: The benefit of adaptivity [J].

Dean, BC ;

Goemans, MX ;

Vondrák, J .

45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2004, :208-217

← 1 2 3 4 →