Bilevel programs are programs where one optimization problem is constrained by the (global) solutions of another optimization problem. Bilevel programs represent hierarchical decision making where two decision makers (optimizers) control a subset of the decision variables. There are many applications of bilevel programs including the allocation of military resources [1] and modeling of different agencies/departments competing for limited resources [2]. In chemical engineering bilevel programs have been used to consider chemical process design with phase equilibrium [3] or plant design under uncertainty and flexibility analysis [4,5]. In biological systems a bilevel formulation has been used to obtain optimal gene knockouts [6].
The novelty of our algorithm is that it can be applied rigorously to nonconvex inner programs and can, under mild assumptions, finitely locate an ε-optimal point along with a guarantee of optimality. Previous approaches either are only applicable to bilevel programs with convex inner programs, or furnish a semi-local solution [7,p. 341], i.e., a local solution in the inner and outer programs. As is typical in global optimization, we assume compact host sets and continuous functions. We further require that equality constraints in the inner problem do not depend on the outer variables. Finally, we assume a regularity condition in the inner program, which is weaker than the Mangasarian-Fromowitz constraint qualification.
We briefly discuss previous literature results and demonstrate issues associated with nonconvexity in the inner program. We then define ε-optimality. The main focus of the presentation is the description of the algorithm. We establish assumptions under which the algorithm terminates finitely. We introduce a set of test problems, and present numerical results for these test problems and for literature examples [8,9]. Finally, we discuss extensions of our work to similar problems.
The algorithm is presented in a branch-and-bound framework; branching is not required for convergence but has potential advantages. For the lower bounding problem, a relaxed program, containing the constraints of the inner and outer programs augmented by a parametric upper bound on the parametric optimal solution function of the inner program, is solved to global optimality. For the case that the inner program satisfies a constraint qualification, a heuristic for tighter lower bounds is presented based on the KKT conditions of the inner program. The upper bounding problem is based on probing the solution obtained by the lower bounding procedure.
[1] J. Bracken and J. T. McGill. Mathematical programs with optimization problems in constraints. Operations Research, 21(1):37-44, 1973.
[2] J. T. Moore and J. F. Bard. The mixed integer linear bilevel programming problem. Operations Research, 38(5):911-921, 1990.
[3] P. A. Clark and A. W. Westerberg. Bilevel programming for steady-state chemical process design. 1. Fundamentals and algorithms. Computers & Chemical Engineering, 14(1):87-97, 1990.
[4] C. A. Floudas, Z. H. Gumus, and M. G. Ierapetritou. Global optimization in design under uncertainty: Feasibility test and flexibility index problems. Industrial & Engineering Chemistry Research, 40(20):4267-4282, 2001.
[5] I. E. Grossmann and K. P. Halemane. Decomposition strategy for designing flexible chemical-plants. AIChE Journal, 28(4):686-694, 1982.
[6] A. P. Burgard and C.D. Maranas. Optimization-based framework for inferring and testing hypothesized metabolic objective functions. Biotechnology and Bioengineering, 82(6):670-677, 2003.
[7 ]J. F. Bard. Practical Bilevel Optimization: Algorithms and Applications. Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht, 1998.
[8] Z. H. Gumus and C. A. Floudas. Global optimization of nonlinear bilevel programming problems. Journal of Global Optimization, 20(1):1-31, 2001.
[9] K. H. Sahin and A. R. Ciric. A dual temperature simulated annealing approach for solving bilevel programming problems. Computers and Chemical Engineering, 23(1):11-25, 1998.