(624a) A New Method for the Global Optimization of Nonlinear Problems with Bilinear Terms

Nonlinear programming problems with bilinear terms can be found in a variety of design problems (e.g. water networks). Existing solution methods include gradient-based algorithms and stochastic approaches (e.g. genetic algorithms, particle swarm optimization) that while capable of finding good feasible solutions with modest computational resources, often fail to find the global optimal solutions to the problem. More reliable methods employ spatial branch-and-bound, where the bilinear terms are replaced by convex over and underestimators (e.g. McCormick linear envelopes). The drawback of such global optimizations solvers is that it may be difficult to prove global optimality, meaning that the lower bound (when minimizing) from the relaxed problem at termination may still be far from the best solution, which naturally increases the chances of failure with respect to finding the global optimal solution.

In this paper, we evaluate the performance of a recently proposed multiparametric disaggregation technique for generalized signomial optimization problems [1], on the optimal design of water-using [2] and wastewater treatment networks [3]. Besides applying it to a problem of industrial relevance instead of performing a proof-of-concept with toy problems [1], the novelty is the use of a binary system for the parameterized variables instead of a decimal numeric system. In such problems, bilinear terms appear in the contaminant mass balances resulting from the product of flows by concentrations.

The proposed approach is to approximate the original NLP by a MILP, where the flowrate variables are disaggregated and the concentration variables are parameterized. Any desired accuracy level can be set for the approximation being the MILP exact in the limit of an infinite number of significant digits. Fortunately, the value of the objective function rapidly approaches the global optimal solution following small increments in the number of significant digits. A given MILP can also be used as an effective initialization method prior to the solution of the original NLP with a local optimization solver, provided that the discretized solution space is not empty.

The results on a set of test problems taken from the literature, for different accuracy levels, show that the method is better suited for wastewater treatment design problems, for which it is more difficult for BARON to reduce the optimality gap to acceptable values. Through the consecutive solution of the MILP for a single increment in accuracy, our new method estimated the optimality gap to almost zero, thus increasing our confidence that the best solutions found are indeed global optima. Regarding the comparison between the two numeric representation systems, the binary had a slight advantage since it could still find good feasible solutions in two cases where the decimal system failed.

[1] J. Teles, P. M. Castro and H. A. Matos. Multi-parametric disaggregation technique for global optimization of nonlinear signomial programming problems. Submitted to Journal of Global Optimization.

[2] J. Teles, P. M. Castro and A. Q. Novais. LP-based solution strategies for the optimal design of industrial water networks with multiple contaminants. Chemical Engineering Science 63 (2008) 376.

[3] P. M. Castro, J. P. Teles, A. Q. Novais. Linear program-based algorithm for the optimal design of wastewater treatment systems. Clean Techn Environ Policy 11 (2009) 83.