一类多维0-1背包问题的约束归并方法

摘要：

提出一种新的关于多维背包(Multi-dimensions Knapsack Problem,MKP)的约束替代问题,MKP是NP-完全问题,称这种约束替代方法为不等式单约束平面生成法.叙述了单约束不等平面生成算法的基本思想,证明了此方法的一些性质及化简问题后所得到的新问题MKPS与原问题MKP的等价性.最后用实例证实了这种化简方法及其有效性.

关键词：优化问题、NP-完全问题、约束归并、单约束

所属期刊栏目：37

分类号：O1(数学)

资助基金：辽宁省教育厅资助项目2004C9

在线出版日期：2008-03-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：71-77