New Implicit Enumeration Method for Polynomial 0-1 Programming

A new implicit enumeration method for polynomial zero-one programming is proposed in this article. By adopting the p-norm surrogate constraint method, a polynomial zero-one programming problem with multiple constraints can be converted into an equivalent polynomial zero-one programming problem with a single surrogate constraint. A new solution scheme is then devised to take the advantage of this prominent feature in carrying out the “fathoming” procedure and the “backtrack” procedure in a searching process of an implicit enumeration. We demonstrate the efficiency of this new algorithm by some promising computational results. Finally, we conclude by proposing certain topics for future research.