Back to Search
Start Over
Global solution of nonlinear mixed-integer bilevel programs
- Source :
- Journal of Global Optimization. 47:557-582
- Publication Year :
- 2009
- Publisher :
- Springer Science and Business Media LLC, 2009.
-
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.
- Subjects :
- Convex hull
Mathematical optimization
Control and Optimization
Karush–Kuhn–Tucker conditions
Applied Mathematics
Function (mathematics)
Management Science and Operations Research
Upper and lower bounds
Computer Science Applications
Interval arithmetic
Global optimization
Mathematics
Parametric statistics
Integer (computer science)
Subjects
Details
- ISSN :
- 15732916 and 09255001
- Volume :
- 47
- Database :
- OpenAIRE
- Journal :
- Journal of Global Optimization
- Accession number :
- edsair.doi...........41e1765c558e1ee18ea64d443fb69bbd