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

作     者：Kosuch, Stefanie Lisser, Abdel 

作者机构：Univ Paris 11 Rech Informat Lab F-91405 Orsay France 

出 版 物：《ANNALS OF OPERATIONS RESEARCH》 (运筹学纪事)

年 卷 期：2010年第176卷第1期

页      面：77-93页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：Static stochastic knapsack problems with random weights Simple recourse Chance constrained Expectation constrained B&B algorithm Stochastic gradient algorithm Arrow-Hurwicz SOCP 

摘      要：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.