Global solution of nonlinear mixed-integer bilevel programs |
| |
Authors: | Alexander Mitsos |
| |
Institution: | (3) PRISM, Computer Sci. Dept. Univ. Versailles, 45, avenue des Etats-Unis, F-78035 Versailles-Cedex, France |
| |
Abstract: | An algorithm for the global optimization of nonlinear bilevel mixed-integer programs is presented, based on a recent proposal
for continuous bilevel programs by Mitsos et al. (J Glob Optim 42(4):475–513, 2008). The algorithm relies on a convergent
lower bound and an optional upper bound. No branching is required or performed. The lower bound is obtained by solving a mixed-integer
nonlinear program, containing the constraints of the lower-level and upper-level programs; its convergence is achieved by
also including a parametric upper bound to the optimal solution function of the lower-level program. This lower-level parametric
upper bound is based on Slater-points of the lower-level program and subsets of the upper-level host sets for which this point
remains lower-level feasible. Under suitable assumptions the KKT necessary conditions of the lower-level program can be used
to tighten the lower bounding problem. The optional upper bound to the optimal solution of the bilevel program is obtained
by solving an augmented upper-level problem for fixed upper-level variables. A convergence proof is given along with illustrative
examples. An implementation is described and applied to a test set comprising original and literature problems. The main complication
relative to the continuous case is the construction of the parametric upper bound to the lower-level optimal objective value,
in particular due to the presence of upper-level integer variables. This challenge is resolved by performing interval analysis
over the convex hull of the upper-level integer variables. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|