(463b) Logic-Based Outer-Approximation Algorithm for Solving Discrete-Continuous Dynamic Optimization Problems

LOGIC-BASED OUTER-APPROXIMATION
ALGORITHM FOR SOLVING DISCRETE-CONTINUOUS DYNAMIC OPTIMIZATION PROBLEMS

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.

References

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.