| 多项式0-1规划中隐枚举算法的改进及应用 |
| |
| 引用本文： | 王军,李端. 多项式0-1规划中隐枚举算法的改进及应用[J]. 系统工程理论与实践, 2007, 27(3): 21-27. DOI: 10.12011/1000-6788(2007)3-21 |
| |
| 作者姓名： | 王军 李端 |
| |
| 作者单位： | 1. 青岛大学,管理科学与工程系,青岛,266071
2. 香港中文大学,系统工程与工程管理系,香港 |
| |
| 基金项目： | 香港大学资助委员会基金;香港中文大学国际学术活动研究生基金 |
| |
| 摘 要： | 提出了一个求解多项式0-1规划问题的隐枚举算法.通过应用p次范数约束划归,多项式0-1规划问题的多个约束可以被一单一等价约束来替代.利用这一显著特性,新算法在搜寻最优解过程中,能改进探寻(fathoming)和折返(backtrack)策略以提高隐枚举法的计算效率.通过一个算例说明这个新算法的计算步骤并对随机产生的问题进行了测试,得到了较好的结果.
|
| 关 键 词： | 非线性整数规划 0-1规划 隐枚举算法 组合优化 |
| 文章编号： | 1000-6788(2007)03-0021-07 |
| 修稿时间： | 2006-11-10 |
A New Implicit Enumeration Method for Polynomial 0-1 Programming and Applications |
| |
| WANG Jun,LI Duan. A New Implicit Enumeration Method for Polynomial 0-1 Programming and Applications[J]. Systems Engineering —Theory & Practice, 2007, 27(3): 21-27. DOI: 10.12011/1000-6788(2007)3-21 |
| |
| Authors: | WANG Jun LI Duan |
| |
| Abstract: | 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. |
| |
| Keywords: | nonlinear integer programming polynomial zero-one programming implicit enumeration combinatorial optimization |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
|
点击此处可从《系统工程理论与实践》下载全文 |
