Global Optimization of Mixed-Integer Bi-Level Programming Problems Via Multi-Parametric Programming

Bi-level (BLPP) and multi-level programming problems (MLPP) arise very often in areas of engineering, control and economics (Vicente, 2001). A key feature of such problems from a mathematical viewpoint is that even for the simplest linear case, a global optimization approach is typically necessary (Floudas, 2001; Visweswaran, 2001). On the other hand, a multi-parametric programming approach applied to certain classes of bi-level programs overcomes the need for global optimization (Faísca et al. 2007).

In this work, we present a multi-parametric programming based approach for mixed-integer bi-level programming problems. We show that, in this case, there is indeed a need for a global optimization approach due to the presence of integer/0-1 variables in the inner/follower's problem. We first employ, a reformulation-linearization technique (Sherali and Adams, 1994) to replace the inner constraint set by its convex hull and then apply a multiparametric programming framework to reach the global optimal solution. Numerical examples and an engineering control application will be provided to illustrate our approach.

References:

Vicente, L., Bi-level programming: Introduction, History and Overview, Encyclopedia of Optimization, Kluwer Academic, Foudas, C. A. & Pardalos, P. M. (ed.), 2001, I, 178-180.

Faísca, N. P.; Dua, V.; Rustem, B.; Saraiva, P. M. & Pistikopoulos, E. N., Parametric global optimisation for bi-level programming, J. Glob. Opt., 2007, 38, 609-623.

Floudas, C. A., Deterministic global optimization: theory, methods and applications, The GOP approach in bi-level linear and quadratic Problems, Kluwer Academic Publishers, 2000, 173-191.

Sherali, H. D. & Adams, W. P., A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems, Discrete Applied Mathematics, 1994, 52, 83-106.

Visweswaran, V., Bi-level programming: global optimization, Encyclopedia of Optimization, Kluwer Academic, Floudas, C. A. & Pardalos, P. M. (ed.), 2001, I, 163-167.