# The ICICS/CS Reading Room

## UBC CS TR-80-04 Summary

- No on-line copy of this technical report is available.

- On the Covering Relaxation Approach for the 0-1 Positive Polynomial Programming Problem, May 1980 Willem Vaessen
Covering relaxation algorithms were first developed by
Granot et al for solving positive 0-1 polynomial programming
(PP) problems which maximize a linear objective function in
0--1 variables subject to a set of polynomial inequalities
containing only positive coefficients [``Covering Relaxation
for Positive 0--1 Polynomial Programs'', Management Science,
Vol. 25, (1979)]. The covering relaxation approach appears
to cope successfully with the non-linearity of the PP
problem and is able to solve modest size (40 variables and
40 constraints) sparse PP problems. This thesis develops a
more sophisticated covering relaxation method which
accelerates the performance of this approach, especially
when solving PP problems with many terms in a constraint.
Both the original covering relaxation algorithm and the
newly introduced accelerated algorithm are cutting plane
algorithms in which the relaxed problem is the set covering
problem and the cutting planes are linear covering
constraints. In contrast with other cutting plane methods
in integer programming, the accelerated covering relaxation
algorithm developed in this thesis does not solve the
relaxed problem to optimality after the introduction of the
cutting plane constraints. Rather, the augmented relaxed
problem is first solved approximately and only if the
approximate solution is feasible to the PP problem is the
relaxed problem solved to optimality. The promise of this
approach stems from the excellent performance of approximate
procedures for solving integer programming problems.
Indeed, the extensive computational experiments that were
performed show that the accelerated algorithm has reduced
both the number of set covering problems to be solved and
the overall time required to solve a PP problem. The
improvements are particularly significant for PP problems
with many terms in a constraint.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.