An Accelerated Covering Relaxation Algorithm for Solving 0-1 Positive Polynomial Programs.
STANFORD UNIV CA DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
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 fx less than or b, where fx 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
- Theoretical Mathematics
- Computer Programming and Software