The bilevel knapsack problem with stochastic right-hand sides

作     者：Ozaltin, Osman Y. Prokopyev, Oleg A. Schaefer, Andrew J. 

作者机构：Univ Pittsburgh Dept Ind Engn Pittsburgh PA 15261 USA 

出 版 物：《OPERATIONS RESEARCH LETTERS》 (运筹学快报)

年 卷 期：2010年第38卷第4期

页      面：328-333页

核心收录：

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

基　　金：National Science Foundation [CMMI-0826141, DMI-0620780] AFOSR [FA9550-08-1-0268] University of Pittsburgh Directorate For Engineering Div Of Civil, Mechanical, & Manufact Inn Funding Source: National Science Foundation 

主　　题：Bilevel programming Stochastic integer programming Value functions 

摘      要：We introduce the bilevel knapsack problem with stochastic right-hand sides, and provide necessary and sufficient conditions for the existence of an optimal solution. When the leader s decisions can take only integer values, we present an equivalent two-stage stochastic programming reformulation with binary recourse. We develop a branch-and-cut algorithm for solving this reformulation, and a branch-and-backtrack algorithm for solving the scenario subproblems. Computational experiments indicate that our approach can solve large instances in a reasonable amount of time. (C) 2010 Elsevier B.V. All rights reserved.