(78a) Global Optimization of a Special Class of Nonlinear Problems

Signomial optimization problems correspond to a very broad class of problems in mathematical programming, of which multilinear problems are a special case, and can be found in a variety of applications (e.g. production planning, location and distribution, chemical process design, pooling and blending). Existing solution methods include standard branch-and-bound and relaxation techniques and are usually concerned with convexification requirements in order to guarantee global convergence. Moreover, they compute an approximate solution of a linear or convex relaxation of the original problem.

This work proposes a new paradigm for the solution of signomial problems. Overall, the signomial problem is approximated to a mixed integer linear problem (MILP) by means of specific power transformations that can be related to the decimal or binary system. In particular, we show how to transform any bilinear term into a sum of linear terms through a multiparametric aggregation technique (MAT) involving powers of ten. Signomial terms can then be recursively constructed through successive applications of MAT for bilinear terms.

The main motivation was to take advantage of the recent developments for state of the art MILP solvers like CPLEX, which enable the solution of problems involving up to tens of thousands binary variables and constraints in a reasonable time. For an idea, a problem involving just a couple of variables and constraints can lead to 40 binary variables, 106 total variables and 77 constraints and be solved in 0.102 CPUs by CPLEX 12.1 on an Intel Core 2 Duo 2.4 GHz when the variables accuracy level is set to 0 decimal places. The returned solution (67.5) is still far from the real optimum of 58.384, which can be found for an accuracy level of 5 decimal places (solved to optimality in 7.46 CPUs involving 140 binary variables, 356 variables and 252 constraints).

The performance of the new approach is illustrated through the solution of a set of test problems taken from the literature and compared to the branch and reduce global optimization algorithm BARON. While BARON is significantly faster in problems involving just a few variables and constraints (0.03 CPUs in the above problem), the optimality gap rapidly increases with the problem size and can remain very large (e.g. 30%) even after a couple of hours of computational time. In contrast, the new approach can provide a very good approximation of the solution, in terms of the number of decimal places, significantly faster. The drawback is there is no lower bound from an obvious relaxation (LP). The optimality gap can however be estimated by measuring the difference in the objective function for two consecutive iterations, which will typically be orders of magnitude tighter for a widely studied problem (wastewater treatment network design).