Premium
On a stochastic bilevel programming problem
Author(s) -
Kosuch Stefanie,
Le Bodic Pierre,
Leung Janny,
Lisser Abdel
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20482
Subject(s) - mathematical optimization , bilevel optimization , knapsack problem , strong duality , linear complementarity problem , lagrangian relaxation , probabilistic logic , mathematics , quadratic programming , optimization problem , linear programming , quadratic equation , computer science , statistics , physics , geometry , quantum mechanics , nonlinear system
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.© 2011 Wiley Periodicals, Inc. NETWORKS, 2012