271219 Logic-Based Outer-Approximation Algorithm for Solving Discrete-Continuous Dynamic Optimization Problems

Wednesday, October 31, 2012: 12:52 PM
325 (Convention Center )
Ruben Ruiz-Femenia, Chemical Engineering Department, University of Alicante, Alicante, Spain, Antonio Flores-Tlacuahuac, Chemical Engineering Dept., Universidad Iberoamericana, Mexico City, Mexico and Ignacio E. Grossmann, Chemical Engineering Department, Carnegie Mellon University, Pittsburgh, PA


Many chemical process systems of practical interest are subject to changes that cause discontinuities in their dynamics. For instance, thermodynamic phases appear and disappear, flow regimes switch from laminar to turbulent and vice versa and fluids in pipes change direction of motion. Dynamic models are also required for the transient phase of continuous processes such as the start-up, shut-down and changeover procedures.

Optimization of discrete-continuous dynamic problems (also referred as hybrid systems) requires the treatment of non-smooth conditions within the problem formulation. These problems can be formulated as mixed integer nonlinear programing (MINLP) problems, that allow to handle logic conditions that lead to non-smoothness [1]. However, the associated computational expense may be high for large systems with many discrete decisions. This is often the case in hybrid systems with switches at any point in time. Complementary formulations also offer an alternative for some classes of disjunctive problems [2]. They can be embedded within a standard nonlinear programming (NLP), as they model disjunctions without the use of binary variables, but the introduction of complements introduces an inherent non-convexity.

Raman and Grossmann [3] generalized the Balas' disjuntive programming theory [4] and developed the Generalized Disjunctive Programming (GDP), as an alternative modeling framework to the traditional mixed-integer formulations for the discrete-continuous optimization problems. While the mixed-integer programming is based entirely on algebraic equations and inequalities, GDP involves Boolean and continuous variables that are specified in algebraic constraints, disjunctions and logic propositions. This alternative mathematical representation of discrete-continuous optimization problems, not only facilitates the modeling, but also keeps the underlying logical structure of the problem, which can be exploited to the development of customized algorithms. Indeed, two methods have been proposed for the case of convex nonlinear GDP, namely, the disjunctive branch and bound method [5] and the logic-based outer-approximation method [6]. The latter method is based on the idea of solving iteratively a NLP subproblem in reduced space that will provide an upper bound, and a master problem reformulated as an MILP by the convex hull of the linearization of the nonlinear inequalities, which will supply a lower bound and new values for the integer variables. In addition, the logic outer approximation algorithm requires solving several NLP subproblems to produce at least one linear approximation for each term in all the disjunctions. This initialization step implies to solve a set covering problem, which is of small size and easy to solve.

In this paper we address the optimization of discrete-continuous dynamic optimization problems that arise in chemical processes. We formulate these problems as dynamic GDP problems for which we examine an extension of the logic-based OA for static system. The logic-based OA leads to a substantial reduction in the size of the problem compared to the traditional OA algorithm, due to the fact that only the constraints that belong to the active terms in the disjunction (i.e., the associated Boolean variable is true) are imposed. The inactive terms are disregarded. Furthermore, the logic-based OA avoids solutions of the NLP subproblems at trivial solutions (e.g. zero flows) and performs the outer approximations of the nonlinear constraints at the optimal values of continuous variables for the corresponding subproblem.

We assess the performance of the proposed approach by solving several examples of increasing complexity: a problem based on an the example presented by Barton and Lee [7]; the diver problem [8]; and the cascading tank problem [9]. We approach the dynamic optimization problem as a multiperiod dynamic optimization problem without an embedded DAE solver. These periods are represented by finite elements in time, with piecewise polynomial representations of the state and controls in each element [2]. It is shown that the logic-based proposed approach leads to significantly reduced computational times compared to those offer by formulating the hybrid problem as a mixed-integer dynamic optimization problem. Furthermore, it is also shown that the computations for the optimization are much more robust than the full-space MINLP counterpart. Thus, this work has shown that the fundamental ideas from logic-based optimization can be applied to the optimization problems with disjunctive dynamic model constraints.


1.            Avraam, M.P., N. Shah, and C.C. Pantelides, Modelling and optimisation of general hybrid systems in the continuous time domain. Computers and Chemical Engineering, 1998. 22(SUPPL.1): p. S221-S228.

2.            Baumrucker, B.T. and L.T. Biegler, MPEC strategies for optimization of a class of hybrid dynamic systems. Journal of Process Control, 2009. 19(8): p. 1248-1256.

3.            Raman, R. and I.E. Grossmann, Modelling and computational techniques for logic based integer programming. Computers and Chemical Engineering, 1994. 18(7): p. 563-578.

4.            Balas, E., Disjunctive Programming. Annals of Discrete Mathematics, 1979. 5: p. 3-51.

5.            Lee, S. and I.E. Grossmann, New algorithms for nonlinear generalized disjunctive programming. Computers and Chemical Engineering, 2000. 24(9-10): p. 2125-2141.

6.            Türkay, M. and I.E. Grossmann, Logic-based MINLP algorithms for the optimal synthesis of process networks. Computers & Chemical Engineering, 1996. 20(8): p. 959-978.

7.            Barton, P.I. and C.K. Lee, Design of process operations using hybrid dynamic optimization. Computers and Chemical Engineering, 2004. 28(6-7): p. 955-969.

8.            Galán, S. and P.I. Barton, Dynamic optimization of hybrid systems. Computers and Chemical Engineering, 1998. 22(SUPPL.1): p. S183-S190.

9.            Till, J., et al., Applied hybrid system optimization: An empirical investigation of complexity. Control Engineering Practice, 2004. 12(10): p. 1291-1303.


Extended Abstract: File Not Uploaded
See more of this Session: Advances In Optimization
See more of this Group/Topical: Computing and Systems Technology Division