Home // ICCGI 2012, The Seventh International Multi-Conference on Computing in the Global Information Technology // View article

Upper Bounds and Optimal Solutions for a Deterministic and Stochastic Linear Bilevel Problem

Authors:
Pablo Adasme
Abdel Lisser

Keywords: bilevel programming, stochastic programming, mixed integer programming

Abstract:
In this paper, we compute upper bounds and optimal solutions for a deterministic linear bilevel programming problem and then, for a stochastic version of this problem. The latter is formulated while adding probabilistic knapsack constraints in the upper level problem of the initial deterministic model. The upper bounds are computed using a Lagrangian iterative minmax algorithm and linear programming relaxations. To this purpose, we first transform both problems into the so called Global Linear Complementarity problems. We then, use these models to derive equivalent mixed integer programming formulations. This allows comparing the iterative minmax algorithm and the linear programming upper bounds with the optimal solution of the problem for the deterministic and stochastic instances as well. Our numerical results show tight near optimal bounds for both, the stochastic and deterministic linear programming relaxations and larger gaps for the iterative minmax algorithm.

Pages: 333 to 340

Copyright: Copyright (c) IARIA, 2012

Publication date: June 24, 2012

Published in: conference

ISSN: 2308-4529

ISBN: 978-1-61208-202-8

Location: Venice, Italy

Dates: from June 24, 2012 to June 29, 2012