A Balasian-Based Algorithm for Zero-One Polynomial Programming

Hamdy A. Taha
Additional contact information
Hamdy A. Taha: University of Arkansas

Management Science, 1972, vol. 18, issue 6, B328-B343

Abstract: A new algorithm is developed for solving zero-one polynomial problems. The algorithm is a direct extension of the well-known Balasian algorithm for zero-one linear programs. The basic idea underlying the development is that every zero-one polynomial programming problem can be converted into an equivalent zero-one linear system with nonlinear secondary constraints representing the polynomial terms. Moreover, the optimal solution to the original polynomial problem must be a feasible solution to the converted linear problem. Thus, the optimal solution is determined by searching for the best solution among the feasible solutions to the linear problem such that the secondary constraints are satisfied. The important point is that the secondary constraints are considered implicitly so that the size of the problem is determined by its equivalent linear form. Computational experience indicates that the new algorithm compares favorably with the existing ones due to Lawler and Bell [Lawler, E., M. Bell. 1967. A method for solving discrete optimization problems. Oper. Res. 15 1098-1112.] and to Watters [Watters, L. J. 1967. Reduction of integer polynomial problems to zero-one linear programming problems. Oper. Res. 15 1171-1174.]. The application of the algorithm to a special class of nonlinear binary problems is also investigated.

Date: 1972
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.18.6.B328 (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:18:y:1972:i:6:p:b328-b343

Access Statistics for this article

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