New reformulation linearization/convexification relaxations for univariate and multivariate polynomial programming problems

This paper is concerned with the global optimization of polynomial programming problems of the type that arise in various location allocation, chemical process, and engineering design contexts. For such problems, we have previously presented a generic reformulation-linearization technique (RLT) to obtain global optimal solutions. We now introduce several new classes of constraints for both univariate and multivariate versions of this problem, including certain simple convex variable bounding types of restrictions that can be used to augment the basic (linear) RLT relaxation in order to yield tighter lower bounds. A constraint selection strategy is also developed to predict and generate only a useful subset of these constraints, so that the size of the resulting relaxation remains manageable. These relaxations are embedded within a globally convergent branch-and-bound algorithm that additionally incorporates certain range-reduction strategies and a new branching variable selection procedure. Computational results using various chemical process, pooling, and engineering design problems from the literature are also presented to demonstrate the viability of the proposed approach.