A platform for research: civil engineering, architecture and urbanism
A platform for research: civil engineering, architecture and urbanism
Efficiently solving linear bilevel programming problems using off-the-shelf optimization software
Abstract Many optimization models in engineering are formulated as bilevel problems. Bilevel optimization problems are mathematical programs where a subset of variables is constrained to be an optimal solution of another mathematical program. Due to the lack of optimization software that can directly handle and solve bilevel problems, most existing solution methods reformulate the bilevel problem as a mathematical program with complementarity conditions (MPCC) by replacing the lower-level problem with its necessary and sufficient optimality conditions. MPCCs are single-level non-convex optimization problems that do not satisfy the standard constraint qualifications and therefore, nonlinear solvers may fail to provide even local optimal solutions. In this paper we propose a method that first solves iteratively a set of regularized MPCCs using an off-the-shelf nonlinear solver to find a local optimal solution. Local optimal information is then used to reduce the computational burden of solving the Fortuny-Amat reformulation of the MPCC to global optimality using off-the-shelf mixed-integer solvers. This method is tested using a wide range of randomly generated examples. The results show that our method outperforms existing general-purpose methods in terms of computational burden and global optimality.
Efficiently solving linear bilevel programming problems using off-the-shelf optimization software
Abstract Many optimization models in engineering are formulated as bilevel problems. Bilevel optimization problems are mathematical programs where a subset of variables is constrained to be an optimal solution of another mathematical program. Due to the lack of optimization software that can directly handle and solve bilevel problems, most existing solution methods reformulate the bilevel problem as a mathematical program with complementarity conditions (MPCC) by replacing the lower-level problem with its necessary and sufficient optimality conditions. MPCCs are single-level non-convex optimization problems that do not satisfy the standard constraint qualifications and therefore, nonlinear solvers may fail to provide even local optimal solutions. In this paper we propose a method that first solves iteratively a set of regularized MPCCs using an off-the-shelf nonlinear solver to find a local optimal solution. Local optimal information is then used to reduce the computational burden of solving the Fortuny-Amat reformulation of the MPCC to global optimality using off-the-shelf mixed-integer solvers. This method is tested using a wide range of randomly generated examples. The results show that our method outperforms existing general-purpose methods in terms of computational burden and global optimality.
Efficiently solving linear bilevel programming problems using off-the-shelf optimization software
Pineda, S. (author) / Bylling, H. (author) / Morales, J. M. (author)
Optimization and Engineering ; 19 ; 187-211
2017-11-04
25 pages
Article (Journal)
Electronic Resource
English
Bilevel programming , Mathematical programming with complementarity conditions , Nonlinear programming , Mixed-integer programming , Optimization solvers Mathematics , Optimization , Engineering, general , Systems Theory, Control , Environmental Management , Operations Research/Decision Theory , Financial Engineering
Efficiently solving linear bilevel programming problems using off-the-shelf optimization software
| Online Contents | 2017
An interior point technique for solving bilevel programming problems
| Online Contents | 2012
An interior point technique for solving bilevel programming problems
| Springer Verlag | 2012
Bilevel Mixed-Integer Linear Programming Model for Solving the Single Airport Location Problem
| Online Contents | 2017
Stochastic bilevel programming in structural optimization
| British Library Online Contents | 2001