Exact solution methodologies for linear and (mixed) integer bilevel programming

Abstract

Bilevel programming is a special branch of mathematical programming that deals with optimization problemswhich involve two decisionmakers who make their decisions hierarchically. The problem's decision variables are partitioned into two sets, with the first decision maker (referred to as the leader) controlling the first of these sets and attempting to solve an optimization problem which includes in its constraint set a second optimization problem solved by the second decision maker (referred to as the follower), who controls the second set of decision variables. The leader goes first and selects the values of the decision variables that he controls.With the leader's decisions known, the follower solves a typical optimization problem in his self-controlled decision variables. The overall problem exhibits a highly combinatorial nature, due to the fact that the leader, anticipating the follower's reaction, must choose the values of his decision variables in such a way that after the problem controlled by the follower is solved, his own objective function will be optimized. Bilevel optimization models exhibit wide applicability in various interdisciplinary research areas, such as biology, economics, engineering, physics, etc. In this work, we review the exact solution algorithms that have been developed both for the case of linear bilevel programming (both the leader's and the follower's problems are linear and continuous), as well as for the case of mixed integer bilevel programming (discrete decision variables are included in at least one of these two problems). We also document numerous applications of bilevel programming models from various different contexts. Although several reviews dealing with bilevel programming ©Springer-Verlag Berlin Heidelberg 2013.