Computing Upper Bounds for a Lbpp with and Without Probabilistic Constraints

In this paper, we compute upper bounds for a generic linear bilevel programming problem (LBPP) using the iterative min-max (IMM) algorithm proposed in [4,5]. Neither in [4] nor in [5] the authors give optimal solutions for this problem or gaps to measure IMM efficiency. To this purpose, we implement the construction method proposed by Jacobsen [3] to generate valid test instances with their respective optimal solutions. Afterward, we add to these valid test instances knapsack probabilistic constraints in the upper-level sub-problem as in [4,5]. The latter allows us to compute upper bounds for stochastic bilevel instances as well. Our numerical results show average relative gaps of 43.97% for the valid test instances and 28.93% while adding probabilistic constraints. © 2011 Springer-Verlag.