(89e) Deterministic Global Optimization Techniques for Solution of Nlp and Minlp Problems Using Piecewise Linear Relaxations with Applications in Metabolic Engineering

Many engineering design and industrial applications require the solution of nonconvex nonlinear optimization problems. Nonconvexity may give rise to multiple local optima leading classical descent or hill-climbing methods to yield local solutions which are far from being globally optimal. Traditional approaches of nonlinear programming are only successful in determination of locally optimal solutions because of the nonconvexities in the optimization problem. Determination of global optima for nonlinear optimization problems has been an important concern for optimization researchers during the last three decades.

Deterministic methods like spatial Branch-and-Bound [3] and Outer-Approximation algorithms [4] depend on the generation of relaxations to the original problems. Numerous methods [2, 5, 8] have been proposed to construct convex relaxations for algebraic functions. Global optimization algorithms, when used with the existing relaxation techniques, may take a signi cant time to converge to the global solution. In this work, a method using Mixed Integer Linear Programming (MILP) based piecewise linear function relaxations has been developed for creation of relaxations of nonconvex expressions. Using McCormick's [5] reformulation method together with the propositional logic constraints, the original nonlinear NLP or MINLP problem is relaxed to a MILP problem. This method is advantageous in cases where the above mentioned relaxation methods fail to generate tighter relaxations, with the reservation that the method requires the solution to a nonconvex MILP problem. The availability of robust MILP solvers may justify the use of this particular technique. The quality of this lower bound can be modi ed by changing the number of piecewise linear regions used in the lower bounding MILP problem.

In this work, piecewise linear relaxation technique is used to determine global solutions to nonconvex NLPs and MINLPs. In particular, a MILP-based bound contraction technique is employed to determine the global solutions of NLP problems and a decomposition based algorithm is used to nd solutions to nonseparable factorable MINLPs. Obviously, global solution of a lower bounding nonconvex MILP at every node in a Branch-and-Bound search tree is not desirable. The MILP-based bound contraction technique is similar to the optimization based bound tightening technique [1, 7] and can be used to guarantee ² convergence of the global solution. Upon obtaining any local solution, it may be possible to tighten the bounds on any variable by solving two MILP problems with an upper bound cut. This technique helps in avoiding branching of the original problem space during Branch-and-Reduce [6] global optimization algorithm. However, the MILP-based bound contraction technique, when implemented on some problems, may require a signi cant amount of time when solved on a single serial computer. This bound tightening technique can be applied on each of the n original variables in the problem, requiring the solution of 2n optimization problems. In order to decrease the computational burden and increase the ef ciency and speedup of the algorithm, the proposed optimization technique can be implemented in parallel. This exploits the fact that the optimization based bound tightening problems are all decoupled from one another. Instead of contracting bounds of every variable, selecting those variables which may contribute the most to the gap between the original nonconvex problem and the relaxed problem can prove to be as effective and still reduce the computational burden.

A decomposition based approach is presented for solving mixed-integer nonlinear programs. The proposed algorithm consists of solving an alternating sequence of MILP lower bounding problems and NLP problems with binary variable xed. The number of major iterations can be signi cantly decreased by the use of piecewise linear relaxations of the nonconvex functions. The introduction of piecewise linear relaxations improves the lower bound on the problem but increases the number of constraints and binary variables in the Relaxed Master Problem MILP. A sequence of valid lower and upper bounds is generated by the algorithm which converge in a nite number of major iterations.

The proposed deterministic global optimization techniques are applied on metabolic engineering problems which require the optimization and modeling of biochemical systems. Optimization of ethanol production for the fermentation pathway in Saccharomyces Cerevisiae using a steady-state Generalized Mass Action (GMA) model is speci cally considered in this work. Numerical results are compared with currently available algorithms, illuminating the potential bene ts of the proposed algorithm.

References

[1] C. S. Adjiman, I. P. Androulakis, and C. A. Floudas. Global Optimization of Mixed-Integer Nonlinear Problems. 46(9):1769ñ1797, 2000.

[2] C. S. Adjiman, S. Dalliwig, C. A. Floudas, and A. Neumaier. A Global Optimization Method, ÆBB, for General Twice- Differentiable Constrained NLPs - I Theoretical Advances. 22(9):1137ñ1158, 1998.

[3] J. E. Falk and R. M. Soland. An Algorithm for Separable Nonconvex Programming Problems. Management Science, 15(9):550ñ569, 1969.

[4] E. P. Gatzke and E. O. Voit. Modeling of Metabolic Systems Using Global Optimization Methods. 2004.

[5] G. P. McCormick. Computability of Global Solutions to Factorable Nonconvex Programs: Part I - Convex Underestimating Problems. Mathematical Programming, 10:147ñ175, 1976.

[6] H. S. Ryoo and N. V. Sahinidis. Global Optimization of Nonconvex NLPS and MINLPs with Application to Process Design. 19(5):551ñ566, 1995.

[7] E. M. B. Smith. On the Optimal Design of Continuous Processes. PhD thesis, Imperial College, London, 1996.

[8] Mohit Tawarmalani and Nikoloas V. Sahinidis. Global Optimization of Mixed-Integer Nonlinear Programs: A Theoretical and Computational Study. Mathematical Programming, October 2002.