(198b) Global Solution of Bilevel Mixed-Integer Nonlinear Programs

A deterministic algorithm for the global solution of bilevel mixed-integer nonlinear programs is presented. The algorithm is rigorous and terminates finitely to a point that satisfies ε-optimality in the upper- and lower-level programs. This is the first deterministic algorithm to do so.

Bilevel programs are programs where one optimization problem (upper-level program) is constrained by the (global) solutions of another optimization problem (lower-level program). Bilevel programs represent hierarchical decision making where two decision makers (optimizers) control a subset of the decision variables. Bilevel programs are used in many applications of (bio-)chemical engineering, e.g., [1,2,3,4]. A major challenge in bilevel programs is nonconvexity of the lower-lever program, in which case traditional methods based on the KKT necessary conditions typically obtain infeasible points. The presence of integer variables gives significant more flexibility in modeling, but further complicates the solution, especially when integer variables are present in the lower-level program. Moore and Bard [5,6] discuss difficulties of the mixed-integer case, in particular that removing the integrality constraints does not necessarily give a relaxation of the bilevel program. Reformulating integer variables using MPEC constraints would not be efficient.

The algorithm presented is based on a recent proposal for continuous bilevel programs [7], however the generalization to mixed-integer bilevel programs is far from trivial. The assumptions necessary for convergence are compact host sets, continuous functions and a suitable regularity condition of the lower-level program. The algorithm proceeds similar to the algorithm by Blankenship and Falk [8] for semi-infinite programs, by adding cuts to the lower bounding problem until the upper bound is guaranteed to generate an ε-optimal point. The upper bounding problem is based on probing the solution obtained by the lower bounding procedure. The cuts used are generated by parametric upper bounds to the lower-level program. In the special case that the lower-level program satisfies a constraint qualification for fixed integer values, the KKT necessary conditions can be used to tighten the lower bound and reduce the number of iterations. Branching can be performed, but is not necessary for convergence.

The presentation gives a motivation and statement for the algorithm along with a proof outline for a finite termination theorem. Then illustrative examples are discussed as well as numerical results from literature examples and new test problems. As is demonstrated in the numerical examples, the proposed algorithm can solve literature problems for which previous contributions have terminated with suboptimal or infeasible points.

[1] 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.

[2] 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.

[3] I. E. Grossmann and K. P. Halemane. Decomposition strategy for designing flexible chemical-plants. AIChE Journal, 28(4):686-694, 1982.

[4] 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.

[5] J. T. Moore and J. F. Bard. The mixed integer linear bilevel programming problem. Operations Research, 38(5):911--921, 1990.

[6] J. F. Bard. Practical Bilevel Optimization: Algorithms and Applications. Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht, 1998.

[7] A. Μitsos, P. Lemodinis and P. I. Barton. Global solution of bilevel programs with a nonconvex inner program. In press: Journal of Global Optimization, October 12, 2007.

[8] J. W. Blankenship and J. E. Falk. Infinitely constrained optimization problems. Journal of Optimization Theory and Applications, 19(2):261--281, 1976.