Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142729 | Operations Research Letters | 2010 | 6 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Osman Y. Özaltın, Oleg A. Prokopyev, Andrew J. Schaefer,