An accelerated covering relaxation algorithm for solving 0–1 positive polynomial programs

The purpose of this note is to present an accelerated algorithm for solving 0–1 positive polynomial (PP) problems. Like our covering relaxation algorithm (Management Science 1979), the accelerated algorithm is a cutting plane method, which uses the linear set covering problem as a relaxation for PP. However, a unique and novel feature of the accelerated algorithm is that it attempts to generate cutting planes from heuristic solutions to the set covering problem whenever possible. Computational results reveal that this strategy of generating cutting planes has led to a significant reduction in the computational time required to solve a PP problem.This research was partially supported by National Sciences and Engineering Research Council Canada Grants 67-4181 and 67-3998, Office of Naval Research Contract N00014-76-C-0418, and National Science Foundation Grant ECS80-22027.