The bilevel knapsack problem with stochastic right-hand sides |
| |
Authors: | Osman Y Özalt?n Andrew J Schaefer |
| |
Institution: | Department of Industrial Engineering, University of Pittsburgh, 1048 Benedum Hall, Pittsburgh, PA 15261, USA |
| |
Abstract: | 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. |
| |
Keywords: | Bilevel programming Stochastic integer programming Value functions |
本文献已被 ScienceDirect 等数据库收录! |
|