An Accelerated Covering Relaxation Algorithm for Solving 0-1 Positive Polynomial Programs.
Abstract
The purpose of this paper is to present an accelerated algorithm for solving 0-1 positive polynomial (PP) problems of finding a 0-1 vector x that maximizes cx subject to f(x) less than or = b, where f(x) = f sub i (x)) is an m-vector of polynomials with nonnegative coefficients. Like our covering relaxation algorithm (1979) the accelerated algorithm is a cutting-plane method in which each relaxed problem is a set covering problem and the cutting planes are linear covering constraints. However by contrast with other cutting-plane methods in integer programming (including our original method), we do not solve the relaxed problems to optimality after the introduction of the cutting-plane constraints. Rather, we first solve each relaxed set-covering problem heuristically and only if the heuristic solution is feasible for PP do we solve the relaxed problem to optimality. The promise of such an approach stems from the excellent performance of the various heuristic algorithms for solving integer programs. Indeed the extensive computational experimentation we performed reveals that the accelerated approach has reduced significantly both the number of covering problems solved to optimality and the computational time required to solve a PP problem. For example the average computational time required to solve a PP problem with 40 variables and an average of 10.5 terms per constraints and 3 variables per term was reduced using the accelerated method from 84.7 to 25.8 seconds while the average number of covering problems solved to optimality was reduced from 11.5 to 3.8. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1980
- Accession Number
- ADA089620
Entities
People
- Daniel Granot
- Frieda Granot
- Willem Vaessen
Organizations
- Stanford University