2021 article
Bilevel Integer Programs with Stochastic Right-Hand Sides
Zhang, J., & Ozaltn, O. Y. (2021, March 8). INFORMS JOURNAL ON COMPUTING.
author keywords: bilevel programming; stochastic programming; integer programming; value function; branch and bound
TL;DR:
An exact value function-based approach to solve a class of bilevel integer programs with stochastic right-hand sides is developed and the integer complementary slackness theorem is generalized to bileVEL integer programs.
(via Semantic Scholar)
UN Sustainable Development Goal Categories
16. Peace, Justice and Strong Institutions
(OpenAlex)
Source: Web Of Science
Added: November 1, 2021
We develop an exact value function-based approach to solve a class of bilevel integer programs with stochastic right-hand sides. We first study structural properties and design two methods to efficiently construct the value function of a bilevel integer program. Most notably, we generalize the integer complementary slackness theorem to bilevel integer programs. We also show that the value function of a bilevel integer program can be characterized by its values on a set of so-called bilevel minimal vectors. We then solve the value function reformulation of the original bilevel integer program with stochastic right-hand sides using a branch-and-bound algorithm. We demonstrate the performance of our solution methods on a set of randomly generated instances. We also apply the proposed approach to a bilevel facility interdiction problem. Our computational experiments show that the proposed solution methods can efficiently optimize large-scale instances. The performance of our value function-based approach is relatively insensitive to the number of scenarios, but it is sensitive to the number of constraints with stochastic right-hand sides.