(264c) Global Optimization of Nonconvex Minlps Using Generalized Reduction Constraints Obtained from Alternative Model Formulations

This paper is concerned with the global optimization of Nonconvex Mixed Integer Nonlinear Programs. These problems arise in many diverse industrial applications, to mention some of them, in Process Network Synthesis, in Pooling Network Systems, in Plant Layout Design and in Power Distribution Systems. In order to improve the computational efficiency of the spatial branch and bound methods for solving these problems, this paper has as major objective to propose a methodology to generate formulations which lead to tighter convex relaxations. This is accomplished by systematically developing and combining a set of alternative model formulations using engineering knowledge and physical insight.

Most of the current approaches to obtain convex relaxations for nonconvex problems rely on the use of predefined convex envelopes or suitable linear outer approximations of the non convex terms that appear in the formulation, Tawarmalani & Sahinidis [2002]. This relaxation procedure leads to formulations where some of the physical laws are often violated (e.g. mass and energy balances are not met). Adding constraints that are redundant in the original formulation and which enforce such laws while keeping the program convex, can strengthen the relaxation.

Redundancy, however, is usually not considered a good practice in process modeling. However, we show that this often has a great impact in the tightness of the final relaxation without incurring in a significant increase of the problem size. The explanation behind this behavior can be obtained by realizing that even when alternative nonconvex representations may contain the same information, their relaxations do not. Sherali and Alameddine [1992] proposed a procedure to improve the representation of the problem when it is relaxed through the generation of redundant constraints in bilinear nonconvex programs. This is accomplished by using pairwise products of the linear inequalities originally present, previous to their linearization. Based on a similar idea Liberti [2004] and Liberti and Pantelides [2006] proposed the "method of reduction constraints" which improves the efficiency of the implementation. However, for the general case, the problem of finding useful redundant constraints systematically remains as a challenge. Revisiting the physical meaning behind the problem may still be required. Previous results in this respect were reported by Tawarmalani & Sahinidis [2002] in the p-q pooling problem and Quesada & Grossmann [1995] in Process Networks design. However, to the best of our knowledge, no systematic methodology based on this approach for more general nonconvex problems has been proposed. It is the aim of this work to formalize and extend this idea to any nonconvex MINLP problem whose physical meaning is perfectly defined.

The main idea of the approach proposed in this paper is to first generate all alternative model formulations based on engineering knowledge. These models are then combined to give rise to a unique formulation that has redundant constraints, which however, may be non redundant in the relaxation. We study the theoretical properties of these formulations, and for the particular case of Process Networks and Power Distribution Networks, a refined strategy is presented that exploits substructures to infer generalized reduction constraints (i.e. constraints that are redundant in the original formulation but not in its relaxation). We show with a number of computational results that in some cases, order of magnitude improvements in the efficiency of the spatial branch and bound method can be achieved when using the proposed formulation. We also compare the proposed approach with traditional modeling approaches that rely on the selection of a single monolithic nonconvex MINLP model.

Liberti L. (2004) Reduction Constraints for the Global Optimization of NLPs. International Transactions in Operation Research Vol 11, No 1, pp 33-41

Liberti L. & Pantelides (2006) An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms. Journal of Global Optimization. Vol 36, Issue 2, pp. 161-189

Quesada & Grossmann (1995) Global Optimization of bilinear process networks with multicomponent flows. Computers Chem. Eng. Vol 19, No 12, pp 1219-1242

Sherali & Alameddine (1992) A new reformulation-linearization technique for bilinear programming problems. Journal of Global Optimization, 2:379-410

Tawarmalani. M & Sahinidis, N. (2002) Convexification and Global Optimization in Continuous and Mixed Integer Nonlinear Programming. Kluwer Academic Publishers