Technical Note—Generalized Covering Relaxation for 0-1 Programs

Daniel Granot and Frieda Granot
Additional contact information
Daniel Granot: University of British Columbia, Vancouver, Canada
Frieda Granot: University of British Columbia, Vancouver, Canada

Operations Research, 1980, vol. 28, issue 6, 1442-1450

Abstract: We construct in this paper a general purpose cutting-plane algorithm for solving the 0-1 polynomial programming problem of finding a 0-1 n vector x = ( x j ) that maximizes c T x subject to f ( x ) ≤ b where f ( x ) = ( f i ( x )) is an m vector of polynomials. The algorithm consists of solving a nested sequence of linear generalized covering problems, i.e., covering problems involving both the original variables x and their complements x̄ = 1 − x . Each problem in the sequence is a relaxation of the original 0-1 polynomial program, and is obtained by adding to its predecessor a small number of generalized covering constraints that are violated by the optimal solution for the preceding generalized covering problem. Over 95% of more than 800 randomly generated problems with up to 70 variables and 50 constraints and mostly up to 5 terms in each constraint were solved by our method in less than 90 seconds of CPU time on an AMDAHL 470 V-6 computer.

Date: 1980
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.28.6.1442 (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:oropre:v:28:y:1980:i:6:p:1442-1450

Access Statistics for this article

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