Note---Efficient Heuristic Algorithms for Positive 0-1 Polynomial Programming Problems

Frieda Granot
Additional contact information
Frieda Granot: University of British Columbia

Management Science, 1982, vol. 28, issue 7, 829-836

Abstract: We develop in this paper two types of heuristic methods for solving the positive 0-1 polynomial programming (PP) problem of finding a 0-1 vector x that maximizes c T x subject to f(x) \le b where c, b \ge 0 and f is an m-vector of polynomials with non-negative coefficients. The various heuristics were first tested on randomly generated sparse problems of up to 50 variables and 50 constraints, and their performance in terms of computational time and effectiveness was investigated. The results were very encouraging. Optimal solutions were consistently obtained by some of the heuristic methods in over 50% of the problems solved. The effectiveness was on the average better than 99% and no less than 96.5%. The computational time using these heuristics is on the average 5% of the time required to solve the PP problems to optimality. Some results for very sparse problems with up to 1,000 variables and 200 constraints are also reported.

Keywords: programming: integer algorithms; heuristic (search for similar items in EconPapers)
Date: 1982
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.28.7.829 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:28:y:1982:i:7:p:829-836

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().