多项式0-1规划中隐枚举算法的改进及应用

A new implicit enumeration method for polynomial zero-one programming is proposed in this paper. 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 computational results and also identify some new application areas. Finally, we conclude the paper by proposing some topics for future research.