Extending a continuous RLT-based algorithm to mixed-integer polynomial problems

In this paper we discuss the extension of an RLT-based algorithm for continuous polynomial optimization problems to handle mixed-integer variables. The chosen approach is a direct one, in which the LP relaxations to be solved at the nodes of the branch-and-bound tree are replaced with MILP relaxations and, therefore, the additional burden caused by the discrete variables is taken care of by the auxiliary MILP solver. One of the main advantages of this approach is that the resulting algorithm inherits all the strengths of the auxiliary MILP solver. We conduct a computational analysis in which we focus on the impact of a number of choices that must be made for the resulting algorithm to be effective at providing good lower and upper bounds upon termination. All the analyses are carried out within RAPOSa, a state-of-the-art global solver for polynomial optimization.