(275e) A Global Optimization Algorithm For Multilinear Programming And Its Application To The Pooling Problem

We have developed an algorithm to efficiently address optimization problems that involve multilinear functions. The original formulation is equivalently transformed into a new one where all non-convexities appear in nonlinear equalities, each of which involves only two variables. The methodology utilizes some variable transformation that is suitable for the convexification of posynomial programs, and we have developed a set of sufficient conditions to determine this suitability [1]. A popular example is the exponential transformation [2] that is widely used in geometric programming [3]. The overall reformulation requires, in the worst case, only one additional variable per original variable, thus maintaining the size of the problem into a minimum. Since all non-convexities are isolated into two-dimensional subspaces of the variable space, an efficient relaxation can be developed. In particular, we apply an iterative piecewise linear underestimation scheme. At every iteration, the partitioning becomes denser only at the interval where the solution of the previous iteration lies. This results into an å-convergent sequence of non-decreasing lower bounds. Furthermore, the solution of each iteration can be derived using information and the data structures of the problem solved at the previous one, considerably reducing the computational time that would, otherwise, be needed. We apply our approach on the well-known pooling problem, that involves bilinear terms and, thus, falls into the multilinear class where our method is applicable. We show that the method exhibits superior performance in a collection of standard benchmark problems [4]. Given the fact that the method does not increase exponentially the size of the problem, it can be used to address real-life large scale pooling problems that are not efficiently tractable by current methods.

[1] C. E. Gounaris and C. A. Floudas, Journal of Global Optimization, Submitted for publication (2007).

[2] C. D. Maranas and C. A. Floudas, Computers & Chemical Engineering 21, 351-369 (1997).

[3] C. A. Floudas, Deterministic Global Optimization, Kluwer Academic Publishers (2000).

[4] M. Tawarmalani and N. V. Sahinidis, Convexification and Global Optimization IN Continuous and Mixed Integer Nonlinear Programming, Kluwer Academic Publishers (2000).