A modeling framework based on bilevel programs involving nonconvex functions and mixed-integer variables is presented. 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 each of two decision makers (optimizers) controls a subset of the decision variables. After discussing existing applications from the literature, new formulations from process design and operations are proposed, including parameter estimation in thermodynamics, scenario-based design and decision making in monopoly markets. In many literature applications and all the proposed problems, the lower-level program is nonconvex and therefore can only be solved rigorously based on recent algorithmic advances [1].

Bilevel programs have been used extensively in operations research for several decades. In this discipline typically the optimizers represent actual decision makers, such as policy makers, military leaders or industrial managers. For instance, Bracken and McGill [2] consider the allocation of military resources; the optimizers model the decision makers of two sides in a war. Fortuny-Amat and McCarl [3] discuss the case of irrigation during limited water supply; here the upper-level program corresponds to the government entity which allocates water to the various farmers; the lower-level programs represent the farmers which given an allocation try to optimize their production. The first application proposed in this talk is decision making by pharmaceutical companies which have monopoly or oligopoly. It is shown that this problem can be cast as a mixed-integer bilevel program with nonconvex objective functions.

Often in operations research linear models are sufficient. However, this is not the case in process design. Clark and Westerberg [4] discuss multi-level and multi-objective optimization problems and show that design under thermodynamic equilibrium can be cast as a bilevel optimization problem. The upper-level optimizer is the designer, while the lower-level optimizer is nature which (at constant temperature and pressure) minimizes Gibbs free energy. Thus, the lower-level program is nonconvex and multi-modal, except for special cases such as ideal solutions [5]. Clark and Westerberg [4] recognize the difficulties of nonconvexity and introduce a variation of the original formulation where a solution is defined as a local solution; this change of what a solution means may be acceptable in some cases, but in many it is not. Another application of bilevel programs in process design is feasibility and flexibility analysis [6,7]; here the upper-level program is the designer, while the lower-level program is the maximization of constraint violation; here a global solution of the lower-level program is necessary, for otherwise an infeasible point may be obtained. Maranas and co-workers [8,9] consider optimal gene knockout; the upper-level program is the designer which tries to obtain maximal yield of a chemical from a microorganism, while the lower-level optimizer is the microorganism which will maximize its growth; for metabolic networks linear formulations are used, so nonconvexity is not an issue.

An extension of feasibility-flexibility analysis is scenario-integrated dynamic optimization. In this talk formulations by Abel and Marquardt [10] are analyzed and extended, and solution methods are proposed. The goal of the formulations in this section is to account for uncertainty in the operation of dynamic systems. During process operation events outside the control of the operator can occur, such as drastic price changes, change of weather or failure of a process component. These events change the dynamics of the system. If these events are not taken into account during the plant design phase the operation may become infeasible and result in catastrophic events. The upper-level objective is to optimize the nominal operation, i.e., the operation without the occurrence of the external events. The lower-level problem is that the scenario operation, i.e., the operation once the event has occurred, is feasible. The global solution of the lower-level programs is mandated similar to feasibility and flexibility problems.

A third application of bilevel programs is based on parameter estimation in thermodynamic equilibrium. In process design and operation typically the phase equilibria are calculated based on activity coefficient models such as the NRTL model. These models contain adjustable parameters which cannot be measured directly, but rather must be estimated based on measured phase-splits. In this talk it is shown that this parameter estimation naturally leads to a bilevel optimization problem. The upper-level program aims in minimizing the error in predictions by adjusting the model parameters, e.g., through a least squares error objective function. The lower-level programs represent the thermodynamic stability requirement, i.e., the predictions must be the global minimum of the Gibbs free energy for the chosen parameter values; equivalent stability criteria [11,12] can be used instead. The lower-level programs are nonconvex and their global solution is necessary.

[1] A. Mitsos, P. Lemonidis, and P. I. Barton. Global solution of bilevel programs with a nonconvex inner program. In press: Journal of Global Optimization, October 12, 2007.

[2] J. Bracken and J. T. McGill. Mathematical programs with optimization problems in constraints. Operations Research, 21(1):37-44, 1973.

[3] J. Fortuny-Amat and B. McCarl. A representation and economic interpretation of a two-level programming problem. Journal of the Operational Research Society, 32(9):783-792, 1981.

[4] P. A. Clark and A. W. Westerberg. Optimization for design problems having more than one objective. Computers & Chemical Engineering, 7(4):259-278, 1983.

[5] W. Robert Smith and R. W. Missen. Chemical Reaction Equilibrium Analysis: Theory and Algorithms. John Wiley & Sons, New York, 1982.

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

[7] C. A. Floudas, Z. H. Gümüs, 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.

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

[9] A. P. Burgard, P. Pharkya, and C. D. Maranas. OptKnock: A bilevel programming framework for identifying gene knockout strategies for microbial strain optimization. Biotechnology and Bioengineering, 84(6):647-657, 03.

[10] O. Abel and W. Marquardt. Scenario-integrated modeling and optimization of dynamic systems. AIChE Journal, 46(4):803-823, 2000.

[11] L. E. Baker, A. C. Pierce, and K. D. Luks. Gibbs energy analysis of phase equilibria. Soc. Petrol. Engrs. J., 22:731-742, 1982.

[12] A. Mitsos and P. I. Barton. A dual extremum principle in thermodynamics. AIChE Journal, 53(8):2131-2147, 2007.