Univariate parameterization for global optimization of mixed-integer polynomial problems

• New approach for transforming polynomial MINLP into MILP.
• Approximating upper bounding and relaxation lower bounding formulations are given.
• Bilinear term is basic building block where one variable is discretized.
• Base-2 to base-10 numeric representation systems can be employed.
• Problem size increases logarithmically with number of discrete points, optimality gap decreases linearly.

This paper presents a new relaxation technique to globally optimize mixed-integer polynomial programming problems that arise in many engineering and management contexts. Using a bilinear term as the basic building block, the underlying idea involves the discretization of one of the variables up to a chosen accuracy level (Teles, J.P., Castro, P.M., Matos, H.A. (2013). Multiparametric disaggregation technique for global optimization of polynomial programming problems. J. Glob. Optim. 55, 227–251), by means of a radix-based numeric representation system, coupled with a residual variable to effectively make its domain continuous. Binary variables are added to the formulation to choose the appropriate digit for each position together with new sets of continuous variables and constraints leading to the transformation of the original mixed-integer non-linear problem into a larger one of the mixed-integer linear programming type. The new underestimation approach can be made as tight as desired and is shown capable of providing considerably better lower bounds than a widely used global optimization solver for a specific class of design problems involving bilinear terms.