Messine, Compact relaxations for polynomial programming problems

Abstract. Reduced RLT constraints are a special class of Reformu-lation-Linearization Technique (RLT) constraints. They apply to noncon-vex (both continuous and mixed-integer) quadratic programming prob-lems subject to systems of linear equality constraints. We present an extension to the general case of polynomial programming problems and discuss the derived convex relaxation. We then show how to perform rRLT constraint generation so as to reduce the number of inequality con-straints in the relaxation, thereby making it more compact and faster to solve. We present some computational results validating our approach