A Hybrid Algorithm for Solving Polynomial Zero-One Mathematical Programming Problems

Abstract

This paper presents an algorithm for solving large-scale polynomial (nonlinear) zero-one programming problems. The procedure incorporates a mixture of pseudo-Boolean concepts and time-proven implicit enumeration procedures. Significant savings in the time required to obtain optimal solutions results from the use of a minimum cover to analyze the future effect of a particular implicit enumeration iteration. Additional improvement is obtained through the use of a term ranking strategy to control the arborization of the implicit enumeration process. Computational experience demonstrates that this algorithm can reduce the magnitude of the computer solution time for large problems from several minutes to a matter of a few seconds.

Notes

Handled by the Department of Applied Optimization.