On a stochastic bilevel programming problem

Stefanie Kosuch, Pierre Le Bodic, Janny Leung, Abdel Lisser

Research output: Contribution to journalArticleResearchpeer-review

16 Citations (Scopus)


In this article, a mixed integer bilevel problem having a probabilistic knapsack constraint in the first level is proposed. The problem formulation is mainly motivated by practical pricing and service provision problems as it can be interpreted as a model for the interaction between a service provider and customers. A discrete probability space is assumed which allows a reformulation of the problem as an equivalent deterministic bilevel problem. The problem is further transformed into a linear bilevel problem, which in turn yields a quadratic optimization problem, namely the global linear complementarity problem. Based on this quadratic problem, a procedure to compute upper bounds on the initial problem by using a Lagrangian relaxation and an iterative linear minmax scheme is proposed. Numerical experiments confirm that the scheme practically converges.

Original languageEnglish
Pages (from-to)107-116
Number of pages10
Issue number1
Publication statusPublished - Jan 2012
Externally publishedYes


  • Bilevel
  • Networks
  • Optimization
  • Pricing
  • Stochastic

Cite this