(239c) Translation of Variables for Different Applications in Process Synthesis

Abstract

The aim of this contribution is to present a special translation of variables, which can be applied to logic-based and mixed-integer programming problems in process synthesis. Our research focused on the development of an alternative convex-hull representation for a logic-based outer-approximation algorithm (OA), implemented in an automated process synthesizer MIPSYN. Three examples were solved in order to compare models with and without translation of variables.

1. Introduction

Recent developments in logic-based optimization (e.g. Grossmann and Biegler, 2004) are regarded as some of the most important achievements for effectively modeling and solving discrete-continuous synthesis problems. One of the possible representations of discrete-continuous problems is the Generalized Disjunctive Programming (GDP), which was developed by Raman and Grossmann (1994) as an extension of the disjunctive programming paradigm developed by Balas (1974). GDP problems could be solved either by transforming it into mixed-integer programs or by the development of specific solution methods, e.g. the branch and bound algorithm with convex relaxation by Lee and Grossmann, 2000. Sawaya (2006) showed that the tightness of convex hull representation of disjunctions could be significantly improved by moving global constraints into representation of disjunctions.

In this contribution we present another idea ? a variable translation in order to have a narrower space of variables, which may then further increases efficiency when solving discrete-continuous problems.

2. Variable translation

In synthesis problems, continuous variables v^s are usually defined within zero lower and non-zero upper bounds and constrained by

                                          v^LOy  ≤ v^s ≤v^UPy                                                                             (1)

in order to force non-zero bounds when alternatives are selected (y = 1). The main idea is to substitute a zero-lower-bounded variable v^s of alternatives (0 ≤ v^s ≤ v^s,UP) by a non-zero-lower-bounded variable (v^LO ≤ v ≤ v^UP), through the use of the following translation equation:

                                                        v^s = v ? v^f(1 ? y)                                                                            (2)

where v^f is an arbitrarily-forced scalar from the interval (v^LO,v^UP) and y is a corresponding binary variable. When an alternative is selected, an integer term v^f(1 ? y) becomes zero and v^s becomes equal to v, and when it is rejected, a value v^f is subtracted from the variable v. When eq. (2) is applied to eq. (1) we obtain

                                          v^f + (v^LO? v^f)y  ≤ v ≤ v^f + (v^UP? v^f)y                                               (3)

Note that when y = 1, it follows that v is constrained within its non-zero bounds, and when y = 0, v becomes v^f. In this way the original space of variable is preserved irrespective of discrete decisions. Intuitively, one could expect that retaining within the narrower original space of variables would increase the efficiency of the GDP. Two additional types were obtained besides a mixed integer type of variable translation (eq. (2)). The following relaxed translation formula is obtained if a binary variable y is relaxed to a continuous variable λ defined between 0 and 1.

                                                        v^s = v ? v^f(1 ? λ)                                                                            (4)

A logic-based form of the variable translation is:

                                                        [Y: v^s = v] v [¬Y:  v^s = v ? v^f]                                                          (5)

where for a Boolean variable Y = true it follows that v^s = v and for Y = false v^s = v ? v^f.

2.1. Alternative logic-based OA

Lee and Grossmann (2000) showed that applying the outer-approximation method to the MINLP reformulation of the convex hull relaxation regarding problem (GDP) reduces to the logic-based OA method by Turkay and Grossmann (1996).

Logic-based OA problems are usually solved through MILP transformation where Boolean variables Ys are replaced by binary variables ys, logical relations are formulated as integer constrains and disjunctives are represented either by big-M or convex hull representation. When a convex hull representation is considered, the following MILP master problem (CCH-MILP) is obtained and when it is reformulated by the translation of variables, using eq. (2), the following alternative MILP master problem (ACH-MILP) is obtained:

where L, SD and D_k are sets of NLP solutions, disjunctives and terms in disjunctives, respectively. The key feature of the alternative outer approximations (ineq. (8)) is that they preserve feasibility when alternatives are not selected when x is set to x^f. This enables the use of variables with non-zero lower bounds. Note that if x^f is set to x^LO, ineq. (6) becomes redundant, if it is set to x^UP, ineq. (7) becomes redundant. If the lower bounds are zero, the problem (ACH-MILP) reduces to the problem (CCH-MILP). The MILP model given above is implemented in the MINLP process synthesizer MIPSYN.

2.2. Implementation in a process synthesizer MIPSYN

Until recently only big-M models were used in MIPSYN, the successor of PROSYN-MINLP (Kravanja and Grossmann, 1994), to solve MINLP synthesis problems. Now, the conventional convex hull and the alternative convex hull formulations, using translation of variables, are implemented in MIPSYN, too. The models are formulated in the most generalized form using various capabilities of the high-level language of GAMS. Data-and-topology independent models were developed in this way.

3. Examples

Example 1: The first example is a network synthesis problem with a simple model but very large-scale combinatorics with 400 binary variables. The objective is to minimize total cost at the fixed demand of the final outflow; x^f was set to x^LO.

The solution statistics until the third major MINLP iteration are reported in Table 1. As can be seen in Table 1, it was impossible with big-M formulation to solve the problem within a reasonable time, whilst both convex hull representations enable the solving of this high-combinatorial problem very quickly. Note that with the same integrality gap and smaller number of constraints, the alternative formulation could solve the problem in only a quarter of the CPU time needed to solve the problem using the conventional convex hull formulation.

Example 2: The second example is the synthesis of a heat exchanger network (HEN) comprising different types of exchangers. The model exhibits moderate complexity and high combinatorics (249 binary variables). Table 2 shows the statistics when x^f was set to x^LO. With respect to the integrality gap, number of iterations, CPU time and number of nodes, both convex hull representations significantly outperform the big-M one, whilst the efficiency of the alternative convex hull formulation is approximately twice that of the conventional formulation.

Example 3: The last, allyl chloride example, is the synthesis of a reactor/separator network within an overall heat integrated process scheme, with a complex model and moderate-size combinatorics (184 binary variables). The overall model is highly nonlinear and nonconvex. Therefore, many numerical and other issues are present which makes any comparison between formulations harder, e.g. due to the effects of nonconvexities it is impossible to compare different formulations based on an integrality gap. Table 3 shows solution statistics until the 17th major MINLP iteration. As can be seen from Table 3, the efficiency of the ACH formulation is almost twice as good as that of CCH and four times better than that of Big-M. It should be noted that selection of the optimal final element in PFR is formulated by big-M constraints, so that the overall process ACH and CCH formulations are, in fact, combined ACH/Big-M and CCH/Big-M formulations.

4. Conclusions

Initial experiences with alternative convex hull representation indicate that the alternative convex hull representation is generally more efficient when solving high-combinatorial problems than the conventional one and has the smallest model sizes. In spite of the above mentioned efficiency, ACH formulations exhibit stronger sensitivity to the effects of nonconvexities, and the model representations are more complicated.

References

Balas, E. (1974). Disjunctive programming: Properties of the convex hull of feasible points, technical report MSRR 348,
Carnegie Mellon University, 1974.

Grossmann,
I. E. and L. T. Biegler (2004). Part II. Future perspective on optimization. Comput Chem Eng, 28(8): 1193-1218.

Kravanja, Z. and
I. E. Grossmann (1994). New Developments and Capabilities in Prosyn - an Automated Topology and Parameter Process Synthesizer. Comput Chem Eng, 18(11-12): 1097-1114.

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

Raman, R. and
I. E. Grossmann (1994). Modeling and Computational Techniques for Logic-Based Integer programming. Comput Chem Eng, 18(7): 563-578.

Sawaya, N. (2006). Reformulations, relaxations and cutting planes for generalized disjunctive programming, Thesis (Ph.D),
Carnegie Mellon University,
Carnegie Mellon University, 2006.

Turkay, M. and
I. E. Grossmann (1996). Logic-based MINLP algorithms for the optimal synthesis of process networks. Comput Chem Eng, 20(8): 959-978.