摘要
提出了一个求解多项式0-1规划问题的隐枚举算法.通过应用p次范数约束划归,多项式0-1规划问题的多个约束可以被一单一等价约束来替代.利用这一显著特性,新算法在搜寻最优解过程中,能改进探寻(fathoming)和折返(backtrack)策略以提高隐枚举法的计算效率.通过一个算例说明这个新算法的计算步骤并对随机产生的问题进行了测试,得到了较好的结果.
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.
出处
《系统工程理论与实践》
EI
CSCD
北大核心
2007年第3期21-27,35,共8页
Systems Engineering-Theory & Practice
基金
香港大学资助委员会基金(CUHK4056/98ENCUHK445/05)
香港中文大学国际学术活动研究生基金
关键词
非线性整数规划
0-1规划
隐枚举算法
组合优化
nonlinear integer programming
polynomial zero-one programming
implicit enumeration
combinatorial optimization
