一种对特殊多维O-1背包问题的约束简化方法
迟东璇
锦州师范学院数学系,
摘要：针对一类组合优化问题-多维0-1背包问题(MKP),这是一个NP-难问题,提出一种能减少求解难度的方法-约束化简方法.定义了MKP的紧约束的概念.提出了一种代替多约束组的计算方法.对于经过替换后所得到的新问题,证明了与其原问题解精度上的等价性.
关键词：NP-难问题化简约束紧约束解精度等价性
分类号：O221.4(运筹学)
资助基金：辽宁省教育厅资助项目(9808111079)
论文发表日期：2001-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：3( 11-13 )
英文信息