无界的背包问题的混合算法外文翻译资料

英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料

---

无界的背包问题的混合算法

Vincent Poirriez, Nicola Yanev, Rumen Andonov

LAMIH/ROI UMR CNRS 8530；Faculty of Mathematics and Informatics；INRIA Rennes-Bretagne Atlantique；Institute of Mathematics and Informatics

关键词:组合优化 整数规划 背包问题 分支界限法 动态规划 算法工程

摘要

论文提出了一种新的方法解决无界的背包问题(UKP),提出了一种新的界限并被证实主导之前的UKP实例的一个特殊的类上的界限。将新的界作用于稀疏动态规划算法创造了一个高效、强大的混合算法,名为EDUK2。该算法利用大多数已知的UKP属性,尤其是多样化的主导关系和重要的周期性价值。大量的计算结果表明,除了极少数情况下之外,EDUK2显著优于MTU2和EDUK，包括现在所知的UKP解法，和众所周知的ILOG的通用数学规划优化器CPLEX。这些实验结果表明,需要对UKP的类实例重新定义,对于创造这样的实例，作者提出了自己的见解。

1介绍

背包问题是一个众所周知的组合优化问题。它的无界问题,UKP(也称为整数背包),定义如下，一个背包的容量而且有n种不同的物品，每个种类的物品有一个利润有一个重量。设 w、p表示向量n的大小。问题是如何最优化的装满这个背包，解这个公式

限制条件

是负的积分n维向量的集合。

许多关于这一问题的特性在过去三十年被发现:[1,4,6,11,10,14],但还没有人能把这个问题完全解出来。感兴趣的读者可以读最近的专著[12]，那里有详细的全面的论述。

在本文中,我们引入一个新的上界,并确定UKP家组。我们也设计一个新算法,该算法结合了动态规划解决UKP的方法。这是第一次,这种方法用于UKP。大量的计算实验证明可以有效地把分支界限算法嵌入到动态规划框架里。这些结果也揭示了UKP实例十分困难。

提出动态规划和分支界限方法相结合的混合算法来解0/1背包问题,和解在[9]的情况下subset-sum问题。使用的形容词“混合”也是为背包问题算法[13](0/1背包问题)和[3](0/1多维背包问题),但这是另一种杂化。

本文的组织结构如下:

第二部分简要总结了问题的基本性质;

第三节呈现一个新的上界和相关的类的实例,它比之前所知界要强大;

第四节致力于EDUK2的描述,一个新算法,该算法利用了所有已知的约束关系成功地结合了多种边界。

在第五节这个算法与其他解决方法将比较。

在第六节我们得出结论。

2．总结已知的约束关系和边界

项目之间的约束关系让搜索空间明显减少了。下面列举所有的主次关系, 可以推导出以下的不等式:

当时

1约束

A．集体约束[1,17]。第个物品集体约束于J，写作 当且仅当alpha;= 1时成立。

这个约束的验证计算很困难,所以它只可以使用动态规划方法。我们所知EDUK(有效的动态规划UKP)[1]是唯一一个实际使用这个属性。

B．极限约束[1]。第个物品极限约束于J，写作当且仅当时成立。这是一个明显的概括前面的约束通过单个物品i复合,而是说次物品。最小的定义极限物品，写作，。

最轻的物品有最大的利润/重量比被称为最好的物品,写成b。表明或者甚至不等式当是的最小公倍数

C．多个约束[10]，物品i是多倍约束于，写作,当且仅当 时成立。

这个约束可以有效地用于预处理,因为它可以相对容易的检验。

D．模块化约束[17]，物品i是模块化约束于，写作当且仅当

时成立。

2边界

[10]: 假设前三项是最大的利润/重量比。让我们设

下面的边界

[4]: 。

这里物品应该是最轻的一个，这个边界强于为特殊的集合UKP

3一个新的UKP上界

在下面的文章中,我们介绍一个新的上界UKP，它是的优化，而且在一般情况不适用于。对于SAW-UKP或特殊UKP家庭,其中包括SC-UKP类(),这个新界比以前的界更严格。

不失一般性,这一节中认为:1是最轻的项集内的物品and.如果所有的然后假设1是最好的物品和比例，改变p为p，，我们实现了目标。如果这样的

一个等价变换, 边界以psi;分开)。也假设没有物品是多远约束。让我们定义以下公式:k固定的,对于所有

定理1

证明：首先对于任何合适的，

，

在这种情况下

对于所有i，

关系[5]意味着所有的物品i多元优化于物品1，而且。。

方程

是一个增函数，而且他的最小值是。Case:在这种情况下

而且

。

让我们设有,上限于，是一类分段线性凸函数。在它的图像上一个已知的点。

一个更好的临界点。在第一个情况的证明中,,给出这个点。当我们可以评价在一点更接近0，。这样的估计在上面的第二种情况，但是这很粗略(因为高估了系数而且在舍入操作中)。

另一种方法是下面的定理，主要思路是可视化图形左边的点。

这是通过改变从物品1到物品k来实现的，当k是是可解的。以

下定理当k=b。

定理2 边界

比经典的上界有力，而且它当c不是时更有力。

证明：证明的方法很简单：。当，类似于定理1的第一种方法，我们发现最好的物品b优于其他所有的物品，从而使得最优解决方法用于背包问题与价值。

很容易可以检验。

此外是一个有趣的方程，并且给出一个更好的上界

当。

下面一般的理论根据观察严格意义上的增加不是的倍数。

定义1.所有实例在时称为SAW-UKP。

备注1.我们用名称SAW的原因是锯状的函数曲线图

定义在而且。SAW-UKP的所有实例经过点，由下图像。

以下条件为为SAW-UKP的必要条件。

引理1如果是一个SAW-UKP，那么。

证明：假设前三项是最大比率，而且

（如上，如果他不是一个实例，改变）。

根据引理1，物品1是最好的。在这种情况下很容易发现。由于定理1和关系，足够证明。因为1应该是最轻的物品，我

们有而且。那么而且。

3.1上界关系的总结

我们在这里总结给出范围之间的关系而且之前所知范围。解决EDUK2的实验将在第五节考虑计算。

SAW-UKP:

(a)SS-UKP

(b)SC-UKP而且

(2)Non-SAW-UKP(SC-UKP当在这个类):

例1(一个SAW UKP，)。n=7;c=2900;I={1;..;7};p=[300;580;301;601;605;322;310];w=[120;245;130;260;310;194;190]。

我们可以计算出q=[_;-4;0.1;0.05;0.0714285;0.297297;0.142857](记住没有定义)因此而且例1所以是一个SAW-UKP。边界是:。最优值是7202。

例2(一个non-SAW-UKP，)。n=3;c=2900;p=[119;297;309];w=[119;120;131]。第二个物品是最好的。我们获得=1.090909和=7149。最优价值7140。

例3(一个non-SAW-UKP，)。。第三个物品是最优的。我们获得。

计算出。最优价值是90。

4该算法的主要组件

下面描述的算法是基于一个方便的组合解决UKP中使用的两种基本方法，即动态规划(DP)和分支界限法(Bamp;B)方法。

动态规划(DP)

一个用于解决UKP的递归算法是

，

当。

符合条件的设置应该包含至少一个物品在一些的最优解。这个集合的基数是任何算法重要的基本公式（6）。我们所知EDUK是唯一一个能有效地使用这个递归的解算器。其实现的主要组件(6)的计算,迭代空间的稀疏表示,阈值的主导地位的使用。切片被定义为y时间间隔，稀疏表示基于函数f的特殊形式。我们所知是一个逐步增加y的功能，而且当所有的skip-point可知时，可以完全被恢复。（后来，将被称为最优状态）

随着容量的周期性已由吉尔摩和戈莫里[ 7 ]描述，称为周期性的水平，适用于任何，有一个最优解当。众所周知，每个存在一个，但是他的价值不容易检测。所以尽管周期性属性可以大大减少搜索空间，它只能被一个DP框架检测。在EDUK这由发现一个容量来实现，这样一个当时有最优解。

最后，DP算法的最优解为所有的y低于c的容量允许递归当容量。

鉴于上述提到的属性，事实上，EDUK表现明显好于最坏的情况下复杂性的递归式。

分支定界

不像DP，算法计算最优解方案只对于给定的一个容量，并且依赖于计算上界的质量，MTU2算法由Martello提出而且Toth使用上界和现在众所周知的变量组合：设z是一个已知的可行解的目标函数值，而且设是一个的上界；如果，那么不管z和那个是最优都可以设置为0.我们说在这种情况下物品j是“fathomed by bounds”。

DP和的混合

有几个补充的方法来整合有范围的知识到DP里去。

1. 第一种方法是使用变量减少组合在预处理阶段减少N
2. 第二种方法是在计算，每个最优状态，一个上界对一个背包问题的c-y容量。如果，z是现在的物品价值，那么状态可以被丢弃。在这种情况下，我们说这个状态是“fathomedby bounds in a Bamp;B context”。这个状态减方案（这里叫做DP的清楚的界限）在稀疏表示迭代的空间显著减少的状态的数量。
3. 第三个解决方法解决一个问题，用算法来实现，这种情况下核心集的一个子集的物品最好的比率。当时问题解决。另外，在DP的一定阶段的状态下作为一个已知可行的解决方案的价值。

4.1 EDUK2算法概述

算法EDUK2，以下给出，是一个EDUK和成分的混合，根据上述给定的集成。基本的EDUK2步骤有：

步骤1：在时间内找最佳物品b，然后找到一个有价值z的初始可行解。除了N，所有的物品都多倍约束于b，这也是在限行时间内完成。

步骤2：减少的物品N，用第三章描述的技术计算一个上界。应用到变量组合减少时间。然后，选择包含c物品的一个子集有最好的比率（尺寸c的核心）

步骤3：为了提高最低的边界，在核心运行一个算法，限制他不超过B节点。

步骤4：运行DP测量界限状态（见4.1.1部分）。

备注2.在当前实现EDUK2中，我们用一个类似于在MTU1中的那个，但是它用计算出上界的能力进一步丰富。参数B和C，通过实验优化并固定在。

4.1.1 DP测量边界状态

一个比步骤4增强版的EDUK操作。它的伪代码在清单1给出。dp-solve功能（states，items，ya，yb）是一个动态的基于递归的编程（6）。它遍历搜索空间的大小h。从一些初始列表的状态states，物品items，dp-solve用极限主导来创建支配自由列表（statesrsquo;，itemrsquo;）物品和状态包括重量在容量空间。这部分的程序对应于原始EDUK。

此外,根据上面给出的第二个集成方法，返回结果列表（statesrsquo;rsquo;，itemrsquo;rsquo;）。这些计算可以提高现在客观的价值z。考虑到这个，函数测深收益以以下方式：对于任何未解决的状态，一个贪婪的解决背包问题方法发现，而且和解决方法一个完成。如果它的价值比z好，这个新的可行解的值代替了旧的。这个DP的功能是新的而且只能具体化EDUK2。

注意到计算所有的最优状态当时足够，

虽然任何背包问题容量可以由计算和之一来解决。

5.性能评价试验

计算实验为了运行：（i）测试的效率配对然后新边界的容量；（ii）展示一些真正困难的实例。不幸的是很少有报道关于实验的例子。因为这个原因我们集中我们的努力在一组基准测试使用：（a）随机生成利润和/或重量与一些相关公式；（b）硬数据集是特别设计的Bamp;B的方法[5]。

生成的主要规则有趣(公平)实例简要概述如下：

1. 实例没有单独的约束（wsd）。这些实例相互不相等的重量然后如果然后对于每个组合。因此,对于与整数数据实例。这可能会导致产生大尺寸的实例的问题，由于算术溢出,需要专用编译器（一个用于EDUK2）。
2. 实例没有集体约束（wcd）。和上面是一样，可以很容易地证明一个充分条件类型的一个

   剩余内容已隐藏，支付完成后下载完整资料

   ---

   资料编号：[29592]，资料为PDF文档或Word文档，PDF文档可免费转换为Word