(514c) Multiparametric Programming Based Algorithms for Bilevel Mixed-Integer Linear and Quadratic Programming Problems

Optimization problems involving two decision makers at two different decision levels are referred to as bilevel programming problems: the first decision maker (upper level; leader) is solving an optimization problem which includes in its constraint set another optimization problem solved by the second decision maker (lower level; follower). Bilevel programming problems are very challenging to solve, even in the linear case. For classes of problems where the lower level problem also involves discrete variables, this complexity is further increased, typically requiring global optimization methods for its solution. Solution approaches for mixed integer bilevel problems with discrete variables in both levels mainly include reformulation approaches [1, 2], branch and bound techniques [3] or genetic algorithms [4], all of which result in approximate solutions.

In this work, we present novel algorithms for the exact and global solution of two classes of bilevel programming problems, namely (i) bilevel mixed-integer linear programming problems (B-MILP) and (ii) bilevel mixed-integer quadratic programming problems (B-MIQP) containing both integer and continuous variables at both optimization levels. Based on multi-parametric theory and our earlier results [5, 6], the main idea is to recast the lower level problem as a multi-parametric programming problem, in which the optimization variables of the upper level problem are considered as parameters for the lower level. The resulting exact parametric solutions are then substituted into the upper level problem, which can be solved as a set of single-level deterministic mixed-integer programming problems. Extensions to problems including right-hand-side uncertainty on both lower and upper levels are also discussed.

References: [1] Mitsos, A. Global solution of nonlinear mixed-integer bilevel programs (2010) Journal of Global Optimization, 47 (4), pp. 557-582.

 [2] Saharidis, G.K., Ierapetritou, M.G. Resolution method for mixed integer bi-level linear problems based on decomposition technique (2009) Journal of Global Optimization, 44 (1), pp. 29-51.

 [3] GümüÅ?, Z.H., Floudas, C.A. Global optimization of mixed-integer bilevel programming problems (2005) Computational Management Science, 2 (3), pp. 181-212.

 [4] Nishizaki, I., Sakawa, M. Computational methods through genetic algorithms for obtaining Stackelberg solutions to two-level integer programming problems(2005) Cybernetics and Systems, 36 (6), pp. 565-579.

 [5] Faísca, N.P., Saraiva, P.M., Rustem, B., Pistikopoulos, E.N. A multi-parametric programming approach for multilevel hierarchical and decentralized optimisation problems (2009) Computational Management Science, 6 (4), pp. 377-397.

 [6] Faisca, N.P., Dua, V., Rustem, B., Saraiva, P.M., Pistikopoulos, E.N. Parametric global optimisation for bilevel programming (2007) Journal of Global Optimization, 38 (4), pp. 609-623.