约束条件下的买方对卖方推荐

定义amn×mn对称矩阵Y=XXTW，其中X如第3节所示。CAC-REC问题可以描述为最大T族（WY）s.T.T族（DbiY）≤ D（i）， 我∈ 英国电信竞赛（DsiY）≤ D（i）， 我∈ 圣赛（CiY）≤ T 我∈ SY=XXT 0（4）式中，W、Dbi、DSI和CIA为下文所述的适当定义的mn×mn对称矩阵。1.W是具有对角权重wij的对角矩阵。2.Dbiis对角矩阵，其中一行由（i，j）索引，如果（i，j）∈ 否则为E和0。3.Dsiis对角矩阵，1表示（k，i）if（k，i）索引的行∈ E和0其他。4.最后，ci是一个包含1/2和0项的矩阵。由行（j，i）和列（k，i）索引的入口等于1/2if（j，i），（k，i）∈ E和（j，k）∈ C.否则为0。我们基于SDP的CAC-REC算法如下：1。求解半有限程序松弛以获得最优解Y.2。使用Y的Cholesky分解[9]，获得g到Y.3对应的向量xij。使用两步舍入程序，随机投影，然后进行阈值舍入，以获得xij的0,1值。在SDP算法的步骤（1）中，使用通用SDP解算器求解上述SDP。第（1）步的输出是一个半限定矩阵Y。在我们算法的第（2）步中，我们使用了一个众所周知的事实，即任何半限定矩阵Y都可以写成Y=VVTW，其中V是一个mn×mn的低三角矩阵。这种分解称为Y的Cholesky分解[9]。V列给出了变量xij的向量解。因此，我们的算法步骤（2）的输出是mn个向量，每个xij对应一个向量。这些向量对应于SDP的最优解。在我们算法的最后一步中，我们使用两步舍入程序转换向量xijpointegral{0，1}值。在第一步中，我们通过arandom投影将xij转换为分数。

也就是说，我们通过从正态分布N（0，1）中选取每个坐标来选取维数mn的随机向量x，并确定每个xi，jas其投影到x的长度。最后，我们对xijan进行排序，并将每个非零值取整为1，前提是这样做不会违反度约束或冲突约束。否则，我们将其设置为CAC Rec的0.4.3 ILP公式。解决SDP公式需要足够大的物理内存来存储mn×mn矩阵Y。在实践中（例如，某一类别的eBay购买图），m（买家数量）和n（卖家数量）的较大值不可避免地限制了SDP方法的适用性。然而，如果我们能将CAC-REC建模为一个整数线性规划（ILP）问题，这个限制就可以得到缓解。为了实现这一目标，我们引入了一个新的0-1变量zi，（j，k），将不等式3表示为一个线性约束。对于每个卖方i，zi，（k，l）等于1，当且仅当两个买方k和l之间存在冲突边，且两条边在图中都是推荐的。使用第3节和第4.1节中的术语，该约束可以描述如下：（1）- xki）+（1- xli）+zi（k，l）≥ 1. 我∈ sk、 l∈ B（5）xki+xli- 2zi（k，l）≥ 0 我∈ sk、 l∈ B（6）X（k，l）∈慈济（k，l）≤ T 我∈ S（7）在约束（6）中，Ci定义如下：Ci={（k，l）∈C |（k，i）∈ E∧ （l，i）∈ E} 。线性冲突约束可以很容易地并入C-REC（问题1）。请注意图中所有卖家的冲突约束总数。然后我们可以得到一个线性规划公式，其中X=[xij]是0-1变量的（mn+c）维列向量。此外，向量m和向量D也可以相应地改变。通过消除存储大尺寸矩阵的需要，现在我们可以使用ILP解算器来处理较大尺寸的CAC问题。

与C-REC相反，在CAC-REC中获得整数解是NP难的。为了进一步提高效率，我们在求解线性规划松弛后使用舍入程序。CAC-REC的LP基本算法如下：1。求解线性规划松弛以获得最优解X.2。将X的第一个元素从最大到最小排序。我们将每个非零值四舍五入为1，前提是这样做不会违反度约束或冲突约束。另外，我们将其设置为0.4.4。在本节中，我们描述并研究了一个简单贪婪算法对该问题的性能。该算法的优点是可扩展性强，在实际应用中提供了高质量的解决方案。CACREC的贪心算法（表示为贪心）如下所示：1。将E中的所有边按重量从大到小排序。2.为了构造最大权子图G′，考虑排序列表中的每条边。如果这样做不违反任何度约束条件约束，则添加此边。3.继续，直到我们到达排序列表的末尾。现在我们将证明贪婪算法性能的理论保证。定理2。设d=maxv∈B |{（v，v′）|（v，v′）∈ C} |。贪婪算法是一种（2+d）近似算法。证据我们使用k-可扩展系统的概念为贪婪算法提供性能保证。Mestre在研究贪婪技术作为近似算法的性能时，引入了k-可扩展系统的概念[7]。定义1（k-可扩展系统[7]）。设U为有限集，F，F 2U，是u的子集的集合。集合系统（U，F）如果满足以下性质，则称为k-可拓系统：1。向下关闭：如果 B和B∈ F、 然后∈ F.2。交换：A，B∈ F和A B、 让x∈U- B是这样的∪ {x}∈ F

然后就有了 B- A、 |Y|≤ k、 这样（B）- Y）∪ {x}∈ F.换句话说，让我们从两个集合A和B中的任意选择开始，这样B就是A的一个扩展。假设有一个元素x，使得加入x的集合A也属于F。那么我们将能够在B中找到一个子集Y，其大小最多为k，这样，如果我们从B中删除Y的元素，并将元素x添加到结果集中，它也将属于集合F。非正式地，Mestre证明，如果所有可行解的集合形成一个k-可拓系统，则算法Greedy给出了一个k-近似算法。也就是说，在任何情况下，贪婪的解与最优解的乘积因子最多为k。我们现在更正式地陈述他的结果。定理3（Mestre[7]）。设（U，F）是一些k的k-可扩展系统→ IR+是U上的正权重函数。然后，贪婪算法给出了一个k-近似算法来求解要求确定最大似然函数的优化问题∈FW（F），其中W（F）=Ps∈FW（s）适用于任何F∈ F.为了将这个结果应用于我们的问题，我们将检查CAC-REC的所有可行解集是否形成（2+d）可扩展系统。对于CAC-REC问题，U=E和F是满足度和冲突约束的G的所有子图的集合。很容易看出（U，F）是向下关闭的。也就是说，从可行解H中删除边将始终导致可行解，因为这不会导致任何违反约束的情况。对于交换属性，考虑n ewedge e=（u，v），u∈ B和v∈ S、 我们有两个观察结果：（1）在u和v处添加e可能会导致违反度约束。然而，这可以通过移除另外两条边来纠正，一条边在u上，另一条边在v上；（2） 添加e可能会导致违反v的冲突约束。

纠正这一点可能需要移除最多d个边，其中d=maxv∈B |{（v，v′）|（v，v′）∈ C} |。因此，我们得到了一个（2+d）可扩展系统。我们指出，这种分析是最坏的情况。在实践中，贪婪显示出远远优越的性能，正如我们稍后使用真实数据集进行的测试所示。5.实验评估为了说明拟议算法的最佳性和可扩展性，我们对C-REC和CAC-REC的真实数据集进行了全面的实验。这些数据集（由Terapeak提供）包括2013年eBay Canada所有类别的三个月交易记录。我们注意到，尽管我们使用了Terapeak的数据，但通过eBay API可以轻松收集类似的数据集。在我们的研究中，我们使用了特定类别（手机和配件）的销售数据，其中包括18742名买家和1884名卖家，在筛选出仅从单一卖家购买的买家和向不超过50名不同买家出售商品的卖家后。然后，我们分别根据总货币采购量和总利润对买家和卖家进行排序。每条边上的重量来自真实世界的销售数据，下面的实验将更详细地解释这些数据。所有实验都在64位Ubuntu12.04桌面上运行，该桌面由3.40GHz*8 Intel Core i7 CPU和3.8GB内存组成。5.1 C-REC我们使用快速线性规划（LP）解算器Gurobifor Matlab在不同尺度下求解C-REC。目的是观察LP方法的可伸缩性。Terapeak是一家电子商务公司，帮助卖家oneBay或亚马逊衡量并提升其销售业绩。

http://www.terapeak.ca/http://www.gurobi.com/0度约束比率：10%0200404050.050.751.002.0%1.5%1.0%0.5%（a）度约束比率：10%02004050所有边缘时间百分比（秒）0.250.500.751.002.0%1.5%1.0%0.5%0.5%（b）度约束比率：20%01002004050所有边缘时间百分比（秒）0.250.500.751.002.0%1.5%（c）度约束比率：30%6010所有边缘时间百分比边缘时间（秒）0.25 0.50 0.75 1.002.0%1.5%1.0%0.5%（d）度约束比率：40%0 10 30 50所有边缘时间（秒）的百分比0.25 0.50 0.75 1.002.0%1.5%1.0%0.5%（e）度约束比率：50%图3:C-REC不同度约束比率的运行时间。所有sce narios的运行时间都呈现出类似的趋势，即，密度较高的C-REC需要更长的时间来求解，并且随着图形大小的增大，运行时间会增加。在排序的买家和卖家之间添加边，我们创建了四个不同密度设置的二分图，大致为0.5%、1.0%、1.5%和2.0%。在amanner中生成的边表示每个卖家都有相同数量的连接买家。例如，如果密度为0.5%，第一个卖家（排名靠前）与前90个买家（从1到90）相连，第二个卖家与11到100个买家相连，依此类推。我们还为每个二部图提取了三个不同大小的子集，即使用总边数的25%、50%和75%（买方和卖方节点的数量相应减少）。优势的权重是买方的总货币购买量（对该类别内的所有卖方）和卖方的总利润（对该类别内的所有买方）的总和。对于二部图中的每个买家（卖家），度约束比是所有候选人中推荐卖家（买家）的最大数量的比例。

我们从集合{0.1,0.2,0.3,0.4,0.5}中选择约束比率来说明它们对运行时间的影响。实验中的每个节点（买方或卖方）都有相同的度约束比。图3显示了不同实验设置的运行时间。每个子图中的四条曲线分别对应于具有不同密度的二部图的结果，即0.5%、1.0%、1.5%和2.0%。最终结果计算为五次运行的平均值。我们做了以下观察：1。较高密度的曲线总是位于较低密度的曲线之上，这表明求解较高密度的C-REC需要较长的时间。具体而言，2.0%密度的C-REC比其他密度较小的C-REC需要更多的时间。2.当我们放大二部图的大小时，运行时间会增加。例如，当我们添加更多边时，2.0%密度的上升曲线变得更陡。我们在其他密度曲线中观察到了类似的趋势，但它们没有2.0%的密度曲线那么明显。3.当degreeconstraint比率变大时，运行时间略有变化。例如，每个度约束比（子图（a）、（b）、（c）、（d）和（e））的所有边的2.0%曲线的运行时间分别为44.67、55.36、55.83、60.08和62.74秒。从图3中，我们观察到，无论我们如何改变二部图的大小和度约束，求解CREC的最大实例只需要大约一分钟。结果表明，C-RECis的LP方法具有很高的可扩展性。5.2 CAC建议现在，我们引入成对买家之间的冲突约束。5.2.1 CAC RECA的SDP公式如第4节所述，CAC REC的SDP方法可通过SDP解算器加舍入程序或贪婪算法近似求解。

我们使用SDPT3[13,14]作为SDP解算器，并编写了一个Python脚本来实现贪婪算法。我们比较了各种方法的解、最优SDP（无舍入解）、舍入SDP和贪婪。SDP方法对CAC-REC的适用性受到物理内存的限制，即需求0。2 0.3 0.4 0.5 0.6度约束率货币（*100万美元）0 1 2 3 4 6可持续发展计划。SDP。舍入贪婪（a）冲突对比率：5%0.20.30.40.50.6度约束比率货币（*100万美元）0 1 2 3 4 6 SDP。SDP。圆贪婪（b）冲突对比率：10%0.20.30.40.50.6度约束比率货币（*100万美元）01 2 3 4 6 SDP。SDP。舍入贪婪（c）冲突对比率：15%0.20.30.40.50.6度约束比率货币（*100万美元）01 2 3 4 6 SDP。SDP。四舍五入贪婪（d）冲突对比率：20%。图4：不同冲突对比率的CAC-REC货币解决方案。当度约束比和约束对比都较低时，贪婪近似于最优解，而带舍入的SDP较弱。存储大尺寸矩阵[6]。解决这个问题的一种方法是将二部图分解为几个独立的子图，这些子图不共享公共的买家或卖家。然后我们可以在每个子图上单独运行SDP解算器，并合并所有结果。考虑到我们在买家和卖家之间创建边的方式，可以实现这一点，即每个卖家在排序的子序列中连接到买家。在下面，我们将在一个小的子图上显示获得的结果，以避免重复比较。我们创建了一个小规模的子图，由前5名卖家和前26名买家组成（按货币排名）。每个卖家与10个买家相连，因此每个买家可以被分配给多个卖家。我们使用两种类型的边权重，money和node-rank。

货币权重的计算方法与C-REC实验中的计算方法相同，即买方的总货币购买量（针对该类别内的所有卖方）和卖方的总利润（来自该类别内的所有买方）之和。当然，可以使用任何单调的权重函数。秩权等于一个大常数（在整个图中，买方和卖方节点的总数，在我们的例子中为20626）与买方秩和卖方秩之和的倒数的乘积。我们通过随机抽样买方对的数量，按照以下可能的买方对总数的百分比，{5%，10%，15%，20%}创建不同数量的冲突买方对。与C-REC类似，我们还为每个节点设置了不同的度约束比率，{20%、30%、40%、50%、60%}。此外，我们对每个卖方的冲突约束使用一个常量（“1”），这意味着每个卖方最多可以接受一对冲突买方。我们使用这个常数来放大冲突约束对小规模子图的影响。对于四舍五入的SDP，我们运行随机四舍五入程序20次，并选择最佳解决方案。图4和图5分别描述了m on ey权重和秩权重的三种方法的比较。在图4中，我们观察到，无论冲突如何，当格蕾丝约束比率小于60%时，三种方法的解决方案非常相似，带舍入的SDP略弱于其他方法。原因是，当程度约束很紧时，每个卖方的冲突约束不太可能被激活，即多个冲突买方很少被推荐给卖方。

当度约束比率和约束对比率都很弱时，这种差异就会出现，而较高的约束对比率会导致舍入和贪婪两种情况下的HSDP性能下降更大（例如，比较子图（c）和（d）中60%度约束比率的条组）。图5显示了这三种方法的类似性能变化趋势。例如，当度约束较弱时，解的差异会变得更大，而具有舍入和贪婪的SDP的性能会随着冲突对比率的增加而逐渐增加。同时，我们也观察到贪婪算法的性能总是优于舍入SDP算法。带舍入和贪婪的SDP都能获得接近最优的解决方案。具体而言，在实验中，GR-EEDYE显示出比理论分析高得多的性能。此外，贪婪最重要的优点是，即使应用于大规模数据集，它也能很好地扩展。我们在图6中展示了它的可伸缩性。我们使用相同的2.0%密度图，大小不同，如0。2 0.3 0.4 0.5 0.6度约束比NK Solution 0 20000 40000 60000 SDP。SDP。舍入贪婪（a）冲突对比率：5%0.20.30.40.50.6度约束比率NK Solution0 20000 40000 60000SDP。SDP。舍入贪婪（b）冲突对比率：10%0.2 0.3 0.4 0.5 0.6度约束比率NK Solution0 20000 40000 60000SDP。SDP。四舍五入贪婪（c）冲突对比率：15%0.20.30.40.50.6度约束比NK Solution0 20000 40000 SDP。SDP。四舍五入贪婪（d）冲突对比率：20%。图5：不同冲突对比率的CAC-REC排名解决方案。贪婪在所有情况下都能获得接近最佳的性能。与Reedy相比，舍入SDP得到的解稍差。C-REC实验。度约束比、冲突对比的设置分别为60%和10%。