基于核的MMKP问题算法研究

郑晓月

（商丘师范学院 计算机与信息技术学院，河南 商丘 476000）

背包核首次应用是在解决大（无关联）背包问题上。Balas和Zemel（1980）根据实验观察到线形松弛背包问题（LKP）的解与求KP问题最优解的不同仅体现在几个元素上，他们将包含这些元素的区间作为核。由于问题求解之前无法精确标识核，他们就通过估计中心元素附近区域的大小用一个近似区间来表示核[1]。使用背包核可以在分支定界（B&B）算法中获得一个较好的下限。

这个近似核虽然使得分支定界算法效率有所提高但是核的大小却是固定的（Martello&Toth，1990）。Pisinger引入了核的动态扩展思想并把它应用到B&B算法中（Pisinger，1994），后来又用于动态规划算法（minknap）（Pisinger，1997）。Pisinger又将这些思想应用于MCKP问题并获得了有效的解决MCKP问题的动态规划算法（Pisinger，1995）。在多维背包问题中，Puchinger，Raidl和Pferschy最近提出了一种新方法用来标识核，并且将其应用于一个模拟框架和一个松弛导向变量区域搜索以获得近似方法用来解决MKP问题[2]。

鉴于核思想成功解决了很多一般背包问题，文中导出一个处理多维多选择背包问题（MMKP）的近似核，并用它精确处理这类问题。用三步连续的过程来定义核。方法是在解空间取一个基点，然后定义一个变量的排序关系。接着这个排序关系将被用来定义基点附近构成背包核的合适子空间。

1MMKP核的确定

据Balas和Zemel的定义，核是背包最优解空间和相关线性背包最优解空间中具有不同值的元素所构成集合的最小区域。精确的定义核C可以这样表述（没有临界元素的情况不算在内）：